题解|Eating Together

思路：dp

设两个二维数组f1与f2，它们的定义如下：

f1[i][j]：前i个数，最后一个数为j，使这i个数为升序的最小改变数

f2[i][j]：前i个数，最后一个数为j，使这i个数为降序的最小改变数

首先，f1与f2的边界条件为：

f1[1][j]=[d[i]=j]

f2[1][j]=[d[i]=j]

然后，经过简单的推理，容易得出dp方程：

f1[i][j]=min{f1[i-1][k]+[j=d[i]]} (1<=k<=j)

f1[i][j]=min{f1[i-1][k]+[j=d[i]]} (j<=k<=3)

最后，把f1[n][1~3]与f2[n][1~3]中的最小值取出来，就是答案。

以下为代码

#include<cstdio>
#include<cstring>
#define min(a,b) ((a)<(b)?(a):(b)) //手打min
int n,d[30010],ans1,ans2,f1[30010][4],f2[30010][4];
int main()
{
    scanf("%d",&n);
    memset(f1,0x3f,sizeof(f1)); //注意初始化
    memset(f2,0x3f,sizeof(f2));
    for(int i=1;i<=n;i++)
        scanf("%d",&d[i]);
    f1[1][1]=f1[1][2]=f1[1][3]=1;
    f1[1][d[1]]=0;
    for(int i=2;i<=n;i++)
        for(int j=1;j<=3;j++)
        {
            if(j!=d[i])
                for(int k=1;k<=j;k++)
                    f1[i][j]=min(f1[i-1][k]+1,f1[i][j]);
            else
                for(int k=1;k<=j;k++)
                    f1[i][j]=min(f1[i-1][k],f1[i][j]);
        }
    f2[1][1]=f2[1][2]=f2[1][3]=1; //复制上面的
    f2[1][d[1]]=0;
    for(int i=2;i<=n;i++)
        for(int j=1;j<=3;j++)
        {
            if(j!=d[i])
                for(int k=j;k<=3;k++) //注意是降序
                    f2[i][j]=min(f2[i-1][k]+1,f2[i][j]);
            else
                for(int k=j;k<=3;k++)
                    f2[i][j]=min(f2[i-1][k],f2[i][j]);
        }
    int ans=0x3f3f3f3f; //注意ans的初值要设为极大值
    for(int i=1;i<=3;i++) //统计答案
        ans=min(ans,min(f1[n][i],f2[n][i]));
    printf("%d\n",ans);
    return 0; //结束
}