Description：

有一个计数器每天记录上一次发生某事件的日期距当天有几天，给出 $n$ 天里计数器的信息，可能有错，求如果这段日期里发生了 $i\in[1,n]$ 此事件计数器的信息最少应该改几个，保证第 $1$ 天发生了事件。

$1\le n \le 100$

Solution：

$DP$ ， $f[i][j][k]$ 表示到了第 $i$ 天发生了 $j$ 次事件上一次发生距当天为 $k$ 的最少修改，转移时枚举当天有没有发生事件，分别转移到 $f[i+1][j+1][0]$ 和 $f[i+1][j][k+1]$ 的状态。初值是 $f[1][1][0]=(val[1]==0?0:1)$

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 110

int val[MAXN];

int f[MAXN][MAXN][MAXN];

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&val[i]);

	memset(f,0x3f,sizeof(f));

	f[1][1][0] = (val[1] == 0 ? 0 : 1);

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

	{

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

		{

			for(int k = 0;k <= i;++k)

			{

				f[i + 1][j + 1][0] = min(f[i + 1][j + 1][0],f[i][j][k] + (val[i + 1] == 0 ? 0 : 1));

				f[i + 1][j][k + 1] = min(f[i + 1][j][k + 1],f[i][j][k] + (val[i + 1] == k + 1 ? 0 : 1));

			}

		}

	}

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

	{

		int ans = 0x3f3f3f3f;

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

		{

			ans = min(ans,f[n][i][j]);

		}

		cout << ans << endl;

	}

	return 0;

}