[bzoj1507][Usaco2009 Hol]Transmission Delay 传输谍延时_动态规划

Transmission Delay 传输谍延时 bzoj-1581 Usaco-2009 Hol

题目大意：题目链接。

注释：略。

---

想法：

动态规划。

首先我们考虑从后往前dp。（最近好多题都是从后往前啊）。

这个题就是如此。

状态：dp[i][j]表示i~n中用了j个1的方案数。

第一问中我们只需要加就行了。

第二问，如果当前位是0的方案比k大，那么我们将这位上添0；

如果当前位是0的方案比k小，我们将这位添1。

最后，附上丑陋的代码... ...

#include <iostream>

#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;

}

小结：好题！