https://www.luogu.org/problemnew/show/P4267

题意：一群奶牛在若干天出逃，农夫从出逃的那天开始记录在本子上记录，每次记录的信息是：最近的上一次出逃是几天前，当天就是0天前。但是有一些信息被篡改了。求：如果在这n天出逃了x次，有可能被篡改天数的最小值。x∈[1,n]都要求。

思路：

一开始自己尝试了设f(i,j):前i天出逃j次对应的最少篡改次数，那么第i天由前i-1天转移而来，要么第i天新出逃，也就是应该记录0，要么应该接着上一天记录数字+1，也就是f(i,j)=min{f(i-1,j-1)+(a[i]!=0),f(i-1,j)+(a[i]!=a[i-1]+1)},但是a[i-1]未必是实际应该记录的值，它也有可能被篡改了。例如样例：1，1，2，0，0，1。f(1,1)=1,本来应该f(2,1)也是1，但是误以为1处实际是1，就搞错了。

后来又改成f(i,j,0/1)+last记录上一个位置实际应该记录的，也失败了。

最后改成设f(i,j,k):前i天出逃j次并且第i天实际应该填k对应的最少篡改次数。

那么f(i,j,0)=min{f(i-1,j-1,x)},x∈[0,n],f(i,j,k)=f(i-1,j,k-1)+(a[i]!=k),过了。

#include<bits/stdc++.h>
using namespace std;
#define maxn 110

int n,a[maxn];

int f[maxn][maxn][maxn];

void debug()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)printf("f[%d][%d][0]=%d,[1]=%d\n",i,j,f[i][j][0],f[i][j][1]);
	}
}

int main()
{
//	freopen("input.in","r",stdin);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)for(int k=0;k<=n;k++)f[i][j][k]=(1<<25);
	f[0][0][0]=0;f[1][1][0]=(a[1]!=0);
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{	
			int minn=(1<<25);for(int k2=0;k2<=n;k2++)minn=min(minn,f[i-1][j-1][k2]);
			f[i][j][0]=minn+(a[i]!=0);
			for(int k=1;k<=n;k++)
			{
				f[i][j][k]=f[i-1][j][k-1]+(a[i]!=k);
			}
		}
	}
	for(int j=1;j<=n;j++)
	{
		int minn=(1<<25);
		for(int k2=0;k2<=n;k2++)minn=min(minn,f[n][j][k2]);
		cout<<minn<<endl;
	}
//	debug();
	return 0;
}