首页 > 代码库 > codeforces 477D
codeforces 477D
题意：给定一个长度<=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\n", 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\n%d\n", ans1, ans2 % M);78 }79 80 int main(){81 while (scanf("%s", s+1) != EOF){82 solve();83 }84 }
codeforces 477D
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。