Welcome To SDIBT ACM-ICPC Online Judge

VIRTUAL JUDGE Recent Contest F.A.Qs Discuss Home ProblemSet Status Ranklist 10 Contest LoginRegister Exam
2017 ACM 集训队预选排名~      报名入口
SDIBT Online Judge WebBoard
[ New Thread ]
Problem 2346 >> 思路
jk11171228 @ 2013-10-08 00:48:04
[ Quote ] [ Edit ] [ Delete ] 1#
转移方程:
dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
长度为i的串,1的个数小于j的总数



然后是求出对应的串
考虑若最左边的‘1’是在第k位的 那么必然有 f[k][l] >= I 而 f[k-1][l] < I
那么其实只要降序找到第一个小于I的 就能确认1的位置
接下来就调整 I 和 l, 相当于求一个子问题。
[Top]  [Previous]  [Next]

HOME Back

한국어 中文 English
All Copyright Reserved 2008-2010 SDIBT TEAM
GPL2.0 2003-2010 HUSTOJ Project TEAM
Anything about the Problems, Please Contact Admin:admin