题解|Eating Together

Eating Together

http://www.nowcoder.com/questionTerminal/b32e7c2ae14e41e5ae56e8e1771faad0

思路: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; //结束
}


全部评论

相关推荐

不愿透露姓名的神秘牛友
12-03 16:28
点赞 评论 收藏
分享
11-18 09:44
Java
小白也想要offer:简历别放洋屁,搞不还还放错了,当然你投外企除外,以上纯属个人观点
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务