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:

 #include <bits/stdc++.h>

 #define M 1000000007

 #define Inf 0x3fffffff

 using namespace std;

 char s[];

 int same[][], f[][], c[][];

 inline void add(int& c, const int &a, const int& b){

      c = a + b;

      if (c >= M) c -= M;

 }

 int bigger(const int& x, const int& y, const int& k){

     if (y <= ) return ;

     int len = same[y][x];

     if (len >= k) return ;

     return s[x+len] >= s[y+len];

 }

 void solve(){

      int n = strlen(s + );

      for (int i = n; i >= ; --i)

           for (int j = i; j <= n; ++j)

               if (s[i] == s[j]) same[i][j] = same[i+][j+] + ;

               else same[i][j] = ;

      for (int i = ; i <= n; ++i)

             f[][i] = ;

      c[][] = f[][];

      for (int i = ; i <= n; ++i){

           for (int j = i; j > ; --j) if (s[j] == ''){

                 add(f[j][i], f[j][i], c[j-][min(i-j, j-)]);

                 if (bigger(j, j--(i-j), i-j+)){

 //                     if (j == 11 && i == 17) printf("%d %d %d\n", j, j-1-(i-j), i-j+1);

                      add(f[j][i], f[j][i], f[j--(i-j)][j-]);

                 }

           }

           for (int j = i; j >= ; --j)

                 add(c[i][i-j+], c[i][i-j],  f[j][i]);

      }

      int ans1 = ;

      for (int i = ; i <= n; ++i)

           add(ans1, ans1, f[i][n]);

      for (int i = ; i <= n; ++i)

          for (int j = i; j <= n; ++j) f[i][j] = Inf;

      for (int i = ; i <= n; ++i)

            f[][i] = ;

      for (int i = ; i <= n; ++i)

          for (int j = ; j <= n; ++j) c[i][j] = Inf;

      c[][] = ;

      for (int i = ; i <= n; ++i){

           for (int j = i; j > ; --j) if (s[j] == ''){

                 f[j][i] =  min(f[j][i], c[j-][min(i-j, j-)] + );

                 if (bigger(j, j--(i-j), i-j+))

                      f[j][i] = min(f[j][i], f[j--(i-j)][j-] + );

           }

           for (int j = i; j >= ; --j)

                     c[i][i-j+] = min(c[i][i-j], f[j][i]);

      }

      int ans2 = Inf, x;

      for (int i = n; i >= ; --i) if (f[i][n] < Inf){

             if (n - i > ) break;

             x = ;

             for (int j = i; j <= n; ++j)

                 x = (x << ) + s[j] - '';

             ans2 = min(ans2, x+f[i][n]);

      }

      if (ans2==Inf)

            for (int i = n-; i >= ; --i) if (f[i][n] < Inf){

                x = ;

                for (int j = i; j <= n; ++j){

                     x = (x << ) + s[j] - '';

                     if (x >= M) x-=M;

                }

                ans2 = (x + f[i][n]) % M;

                break;

            }

      printf("%d\n%d\n", ans1, ans2 % M);

 }

 int main(){

     while (scanf("%s", s+) != EOF){

          solve();

     }

 }

巴特西

codeforces 477D

最新文章

热门文章