题解：洛谷P2929 [USACO09HOL] Transmission Delay G

给出 $N (1 \leq N \leq 2000)$ 表示 $01$ 串的长度， $D(O \leq D < N)$ 表示 $0$ 或 $1$ 的最大偏离距离，一个长度为 $N$ 的 $01$ 串和一个整数 $K(1 \leq K \leq10^8)$，请计算传输延迟发生后一共有多少种可能的 $01$ 串，以及其中第 $K$ 大的串是什么。

洛谷

思路

首先这是一个分成两问的 DP 问题。通过原题，$01$ 串中两种位各自的数量不会发生变化，所以对于 DP 的状态，我们可以选用 $0$（或 $1$ ）的数量，即：$f[i][j]$ 表示 $i…n$ 为中使用 $j$ 个 $0$ 的方案数，这里倒着处理是为了求第二问。

另外，已知 $K(1 \leq K \leq10^8)$ ，如果 $f$ 数组的某一位超过 $10^8$ 那么它就会被取模，这会导致错误，因此我们开一个 $g$ 和 $f$ 的操作基本一致，但是如果某一位超过 $10^8$ ，就直接将其改为 $10^8+1$。

具体的转移还是比较直接的。

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long
mt19937 rnd(time(NULL));

const int mod=100000000;

int n,d,k;
string s; 

int f[2005][2005],g[2005][2005]; //f:Question 1; g:Question 2
int cn0[2005],cn1[2005]; // 记录0和1的位置

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	cin>>n>>d>>k>>s;
	s=" "+s;
	
	int l0=0,l1=0;
	for(int i=n;i>0;i--)
	{
		if(s[i]=='0')
		{
			cn0[++l0]=i;;
		}
		else
		{
			cn1[++l1]=i;;
		}
	}
	
	
	f[n+1][0]=g[n+1][0]=1;
	for(int i=n+1;i>1;i--)
	{
		for(int j=0;j<=l0;j++)
		{
			if(f[i][j])
			{
				if(j!=l0&&abs(i-1-cn0[j+1])<=d) //当前位选择0
				{
					if(!(j+l1!=n-i+1&&cn1[n-i+2-j]-i+2>d))
					{
						f[i-1][j+1]=(f[i-1][j+1]+f[i][j])%mod;
						g[i-1][j+1]=g[i-1][j+1]+g[i][j];
						g[i-1][j+1]=min(g[i-1][j+1],mod+1);
					}
				}
				
				if(j+l1!=n-i+1&&abs(i-1-cn1[n-i+2-j])<=d) //当前位选择1
				{
					if(!(j!=l0&&cn0[j+1]-i+2>d))
					{
						f[i-1][j]=(f[i-1][j]+f[i][j])%mod;
						g[i-1][j]=g[i-1][j]+g[i][j];
						g[i-1][j]=min(g[i-1][j],mod+1);
					}
				}
			}
//			;cout<<f[i-1][j+1]<<" "<<f[i-1][j]<<"\n";
		}
	}
	
	cout<<f[1][l0]<<"\n";
	
	for(int i=1;i<=n;i++)
	{
//		cout<<"\n"<<g[i+1][l0-1]<<" "<<k<<"\n";
		if(g[i+1][l0-1]>=k) // 如果当前位为0的方案多于k，就输出0，否则输出1
		{
			cout<<0;
			l0--;
		}
		else
		{
			cout<<1;
			k-=g[i+1][l0-1];
		}
	}
	
	return 0;
}

---