【BZOJ】1609: [Usaco2008 Feb]Eating Together麻烦的聚餐

【算法】动态规划

【题解】DP有个特点(递推的特点)，就是记录所有可能状态然后按顺序转移。

最优化问题中DP往往占据重要地位。

f[i][j]表示前i头奶牛，第i头改为号码j的最小改动数字，这样每头奶牛改为哪个编号的方案全部记录了，转移可以保证最优。

正反各做一次。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=30010;
int n,f[maxn][4],a[maxn];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    f[0][1]=f[0][2]=f[0][3]=0;
    for(int i=1;i<=n;i++)
    {
        f[i][1]=f[i-1][1]+(a[i]!=1);
        f[i][2]=min(f[i-1][1],f[i-1][2])+(a[i]!=2);
        f[i][3]=min(min(f[i-1][1],f[i-1][2]),f[i-1][3])+(a[i]!=3);
    }
    int ans=min(min(f[n][1],f[n][2]),f[n][3]);
    f[n+1][1]=f[n+1][2]=f[n+1][3]=0;
    for(int i=n;i>=1;i--)
    {
        f[i][1]=f[i+1][1]+(a[i]!=1);
        f[i][2]=min(f[i+1][1],f[i+1][2])+(a[i]!=2);
        f[i][3]=min(min(f[i+1][1],f[i+1][2]),f[i+1][3])+(a[i]!=3);
    }
    ans=min(ans,min(f[1][1],min(f[1][2],f[1][3])));
    printf("%d",ans);
    return 0;
}