题解 P2929 【[USACO09HOL]传输延迟Transmission Delay】

· · 题解

这题是个dp。

定义方程f[i][j]表示从n~i，用了j个0的方案数。要n~i倒着处理是为之后的第k大做帮助。

第一问就直接dp，我们记录下p0[i],p1[i]分别表示从左往右第i个0的位置，第i个1的位置。转移的时候根据当前位放0还是放1，且是否满足距离小于等于d，计算即可。

然后对于第二问，我们这么做：

以上所有说的可以放0或放1都是建立在题目要求的前提下的，即距离不超过d

然后我们有一个问题了：如果方案数超过k的超过太多了怎么办？按照题意来说我们应该是要%10^8的，但是由于要求后面的第k大需要用到这个方案数，如果我们直接%10^8，就会导致结果不正确了。

对于这个问题我们再开一个g[i][j]也记录方案数，如果g[i][j]>10^8了就把它设成10^8+1，然后之后算第k大的时候就用g[i][j]当做方案数，这样就没事了。

下面放代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 2010;
const int MOD = 1e8;
int n, d, k, cnt0 = 0, cnt1 = 0;
int p0[N], p1[N], f[N][N], g[N][N];
char s[N];

int main()
{
    scanf("%d%d%d", &n, &d, &k);
    scanf("%s", s+1);
    for (int i = 1; i <= n; i ++)
        if (s[i] == '0') p0[++ cnt0] = i;
        else p1[++ cnt1] = i;
    f[n+1][0] = g[n+1][0] = 1;
    for (int i = n; i >= 1; i --)
        for (int j = 0; j <= min(n-i+1, cnt0); j ++){
            int k = n-i+1-j;
            if (j && abs(p0[cnt0-j+1]-i) <= d){
                f[i][j] += f[i+1][j-1];
                if (f[i][j] > MOD) f[i][j] -= MOD;
                g[i][j] = min(g[i][j]+g[i+1][j-1], MOD+1);
            }
            if (k && abs(p1[cnt1-k+1]-i) <= d){
                f[i][j] += f[i+1][j];
                if (f[i][j] > MOD) f[i][j] -= MOD;
                g[i][j] = min(g[i][j]+g[i+1][j], MOD+1);
            }
        }
    printf("%d\n", f[1][cnt0]);
    int s0 = cnt0, s1 = cnt1;
    for (int i = 2; i <= n; i ++){
        if (s0 && abs(p0[cnt0-s0+1]-i+1) <= d){
            if (g[i][s0-1] >= k) s0 --, putchar('0');
            else s1 --, k -= g[i][s0-1], putchar('1');
        } else s1 --, putchar('1');
    }
    if (s0) putchar('0'); else putchar('1');
    return 0;
}