题意：给定一个长度<=5000的二进制字符串S，以及一个初始为0的n，有一下两种操作：
1. 输出n(n>=1并且为2进制形式输出)
2.n=n+1
每次选择一种操作。。
求：1.有多少方案能构成该字符串 (%(10^9+7))
2.最少需要多少次能构成该字符串(%(10^9+7))
思路：
对于第一问：
能容易想到O(n^3)的dp
f[i][j] += f[k][i-1](其中[k,j-1]构成的数<=[i, j]组成的数，并且i,k位置为'1')
但是这样时限上显然不够，因为比较大小太耗时间了。。
由于是01串，我们可以先预处理same[i][j]表示以i开头和以j开头的数字最多多少个相同的。。这样判断就可以O(1)了
对于第二问：
还是可以用dp。。
f[i][j]表示以j结尾，[i, j]为最后一个数时最少分为几段。。思路跟上面差不多。。
但是比较大小可能需要一点技巧。。
基于最后结尾的数多一位，那么add操作次数*2，那么也就是说当最后的数很大是（add>=|S|），越小的结尾的数越优
所以，对于最后结尾的数比较小的，直接算出来，因为答案不会很大。。
否则的话，直接找结尾的数最小的就是最优解了。
当然，也可以基于上面的结论直接贪心。。
code:
1 #include <bits/stdc++.h> 2 #define M 1000000007 3 #define Inf 0x3fffffff 4 using namespace std; 5 char s[5100]; 6 int same[5001][5001], f[5001][5001], c[5001][5001]; 7 8 inline void add(int& c, const int &a, const int& b){ 9 c = a + b; 10 if (c >= M) c -= M; 11 } 12 13 int bigger(const int& x, const int& y, const int& k){ 14 if (y <= 0) return 0; 15 int len = same[y][x]; 16 if (len >= k) return 1; 17 return s[x+len] >= s[y+len]; 18 } 19 20 void solve(){ 21 int n = strlen(s + 1); 22 for (int i = n; i >= 1; --i) 23 for (int j = i; j <= n; ++j) 24 if (s[i] == s[j]) same[i][j] = same[i+1][j+1] + 1; 25 else same[i][j] = 0; 26 for (int i = 1; i <= n; ++i) 27 f[1][i] = 1; 28 c[1][1] = f[1][1]; 29 for (int i = 2; i <= n; ++i){ 30 for (int j = i; j > 1; --j) if (s[j] == '1'){ 31 add(f[j][i], f[j][i], c[j-1][min(i-j, j-1)]); 32 if (bigger(j, j-1-(i-j), i-j+1)){ 33 // if (j == 11 && i == 17) printf("%d %d %d ", j, j-1-(i-j), i-j+1); 34 add(f[j][i], f[j][i], f[j-1-(i-j)][j-1]); 35 } 36 } 37 for (int j = i; j >= 1; --j) 38 add(c[i][i-j+1], c[i][i-j], f[j][i]); 39 } 40 int ans1 = 0; 41 for (int i = 1; i <= n; ++i) 42 add(ans1, ans1, f[i][n]); 43 for (int i = 0; i <= n; ++i) 44 for (int j = i; j <= n; ++j) f[i][j] = Inf; 45 for (int i = 1; i <= n; ++i) 46 f[1][i] = 1; 47 for (int i = 0; i <= n; ++i) 48 for (int j = 0; j <= n; ++j) c[i][j] = Inf; 49 c[1][1] = 1; 50 for (int i = 2; i <= n; ++i){ 51 for (int j = i; j > 1; --j) if (s[j] == '1'){ 52 f[j][i] = min(f[j][i], c[j-1][min(i-j, j-1)] + 1); 53 if (bigger(j, j-1-(i-j), i-j+1)) 54 f[j][i] = min(f[j][i], f[j-1-(i-j)][j-1] + 1); 55 } 56 for (int j = i; j >= 1; --j) 57 c[i][i-j+1] = min(c[i][i-j], f[j][i]); 58 } 59 int ans2 = Inf, x; 60 for (int i = n; i >= 1; --i) if (f[i][n] < Inf){ 61 if (n - i > 20) break; 62 x = 0; 63 for (int j = i; j <= n; ++j) 64 x = (x << 1) + s[j] - '0'; 65 ans2 = min(ans2, x+f[i][n]); 66 } 67 if (ans2==Inf) 68 for (int i = n-20; i >= 1; --i) if (f[i][n] < Inf){ 69 x = 0; 70 for (int j = i; j <= n; ++j){ 71 x = (x << 1) + s[j] - '0'; 72 if (x >= M) x-=M; 73 } 74 ans2 = (x + f[i][n]) % M; 75 break; 76 } 77 printf("%d %d ", ans1, ans2 % M); 78 } 79 80 int main(){ 81 while (scanf("%s", s+1) != EOF){ 82 solve(); 83 } 84 }