P7793 [COCI2014-2015#7] ACM 题解

· · 题解

更好的阅读体验

很有趣的 DP 题。

规定 Stjepan 的编号为 0，Ivan 为 1，Gustav 为 2。

定义：f_{i,a,b,c,d} 表示当前做到第 i 个任务，做题选手顺序为 a，b，c，且当前题目由编号为 d 的人完成时的最优解。

例：f_{5,2,0,1,0} 表示做题选手顺序为 Gustav（2），Stjepan（0），Ivan（1），且当前题目是由 Stjepan（0）在完成第 5 道题目时的最优解。

初始化：一开始将 f 数组打上 +\infty；f_{1,a,b,c,a} 显然就等于 d_{a,1}。

转移思路：判断上个任务是由自己做优秀还是由排列中的前一个人完成优秀。（本题核心）

答案：最后一个任务一定是由排列中的最后一个人完成的，即 f_{n,a,b,c,c}。

#include<bits/stdc++.h> 
using namespace std;
const int maxn=200005;
int n,d[3][maxn],f[maxn][3][3][3][3],ans=1<<30;
int read(){
    char ch=getchar();int ret=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') ret=ret*10+(ch&15),ch=getchar();
    return ret*f;
}
int main(){
    n=read();
    for(int i=0;i<3;i++)
    for(int j=1;j<=n;j++)
      d[i][j]=read();

    for(int i=0;i<=n;i++)
    for(int a=0;a<3;a++)
    for(int b=0;b<3;b++)
    for(int c=0;c<3;c++)
    for(int d=0;d<3;d++)
      f[i][a][b][c][d]=1<<30;//初始化，用memset会MLE

    f[1][0][1][2][0]=d[0][1];
    f[1][0][2][1][0]=d[0][1];
    f[1][1][0][2][1]=d[1][1];
    f[1][1][2][0][1]=d[1][1];
    f[1][2][0][1][2]=d[2][1];
    f[1][2][1][0][2]=d[2][1];//f[1][a][b][c][a]=a[a][1]：第一个任务只能由排列中的第一个人完成，其最优解为第一个人对于这道题目估计的难度

    for(int i=2;i<=n;i++){
        f[i][0][1][2][0]=f[i-1][0][1][2][0]+d[0][i];
        f[i][1][0][2][1]=f[i-1][1][0][2][1]+d[1][i];
        f[i][1][2][0][1]=f[i-1][1][2][0][1]+d[1][i];
        f[i][0][2][1][0]=f[i-1][0][2][1][0]+d[0][i];
        f[i][2][0][1][2]=f[i-1][2][0][1][2]+d[2][i];
        f[i][2][1][0][2]=f[i-1][2][1][0][2]+d[2][i];//1至i的任务都是由第一个人完成的，继承前一状态+当前代价即可 
        if(i<2) continue; 
        f[i][0][1][2][1]=min(f[i-1][0][1][2][0],f[i-1][0][1][2][1])+d[1][i];
        f[i][0][2][1][2]=min(f[i-1][0][2][1][0],f[i-1][0][2][1][2])+d[2][i];
        f[i][1][0][2][0]=min(f[i-1][1][0][2][1],f[i-1][1][0][2][0])+d[0][i];
        f[i][1][2][0][2]=min(f[i-1][1][2][0][1],f[i-1][1][2][0][2])+d[2][i];
        f[i][2][0][1][0]=min(f[i-1][2][0][1][2],f[i-1][2][0][1][0])+d[0][i];
        f[i][2][1][0][1]=min(f[i-1][2][1][0][2],f[i-1][2][1][0][1])+d[1][i];//当前任务由第二个人完成，比较上一个任务是由自己完成好还是别人完成好
        if(i<3) continue;
        f[i][0][1][2][2]=min(f[i-1][0][1][2][1],f[i-1][0][1][2][2])+d[2][i];
        f[i][0][2][1][1]=min(f[i-1][0][2][1][2],f[i-1][0][2][1][1])+d[1][i];
        f[i][1][0][2][2]=min(f[i-1][1][0][2][0],f[i-1][1][0][2][2])+d[2][i];
        f[i][1][2][0][0]=min(f[i-1][1][2][0][0],f[i-1][1][2][0][2])+d[0][i];
        f[i][2][0][1][1]=min(f[i-1][2][0][1][0],f[i-1][2][0][1][1])+d[1][i];
        f[i][2][1][0][0]=min(f[i-1][2][1][0][0],f[i-1][2][1][0][1])+d[0][i];//当前任务由第三个人完成，比较上一个任务是由自己完成好还是别人完成好
    }
    ans=min(ans,f[n][0][1][2][2]);
    ans=min(ans,f[n][0][2][1][1]);
    ans=min(ans,f[n][1][0][2][2]);
    ans=min(ans,f[n][1][2][0][0]);
    ans=min(ans,f[n][2][0][1][1]);
    ans=min(ans,f[n][2][1][0][0]);//无论如何，最后一个任务一定是由排列中的最后一个人完成的
    printf("%d\n",ans); 
    return 0;
}

附录：本思路的另一种写法。

Idea：@WAWA_QWQ。

排版 & 格式：@Rigel。