自动搬运

查看原文

来自洛谷，原作者为

	WAWA_QWQ 这个家伙神经病，什么也没有留下

搬运于2025-08-24 22:33:08，当前版本为作者最后更新于2024-08-15 08:32:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

更好的阅读体验

很有趣的 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：

排版 & 格式：