标签：DP
题目
问题描述
Lyra 和 Evan 在玩⼀款双⼈游戏，这款游戏共有 n 个关卡，m 个⼈物，第 i 关如果使⽤第 j 个⼈物则通过时间为 ti,j，两⼈并没有合作的意识，所以如果两个⼈分别使⽤⼈物 j1, j2，则通关时间为 ti,j1 + ti,j2。
| 两⼈同⼀关不可以使⽤同⼀个⼈物，相邻两关之间两⼈需要分别选择⼈物，第⼀关选择⼈物不需要时间，以后每两关之间要从⼈物 a 切换到⼈物 b 需要 k | a − b | 的时间，两个⼈切换⼈物的时间为各⾃切换⼈物的时间总和。 |
在朋友⾯前夸下海⼜的 Lyra 和 Evan 现在不得不表演最快速度通关的⽅法，于是他们找到了你，希望你能求出通关的最⼩总时间。
分析
可以很轻松的推出20pts的暴力DP
然后更换一下DP顺序就可以得到40pts
考前的最后一场模拟赛了orz
把人物选择位置放在二维平面上，发现两个点的最短路一定是两个方向的折线，考虑四个方向分别做DP
时间复杂度\(O(nm^2)\)
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define ll long long
#define reg(i,x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
#define inf 1e18
const int maxn=306;
int n,m,K;
ll ans=inf,f[maxn][maxn]={0},a[maxn][maxn];
int main(){
n=read(),m=read(),K=read();
rep(i,1,n)rep(j,1,m)a[i][j]=read();
rep(i,1,n){
rep(j,1,m)rep(k,1,m)
if(j!=k)f[j][k]=f[j][k]+a[i][j]+a[i][k];
rep(j,1,m)f[j][j]=inf;
rep(j,1,m)rep(k,1,m){
if(j<m)f[j+1][k]=min(f[j+1][k],f[j][k]+K);
if(k<m)f[j][k+1]=min(f[j][k+1],f[j][k]+K);
}
rep(j,1,m)dep(k,m,1){
if(j<m)f[j+1][k]=min(f[j+1][k],f[j][k]+K);
if(k>1)f[j][k-1]=min(f[j][k-1],f[j][k]+K);
}
dep(j,m,1)rep(k,1,m){
if(j>1)f[j-1][k]=min(f[j-1][k],f[j][k]+K);
if(k<m)f[j][k+1]=min(f[j][k+1],f[j][k]+K);
}
dep(j,m,1)dep(k,m,1){
if(j>1)f[j-1][k]=min(f[j-1][k],f[j][k]+K);
if(k>1)f[j][k-1]=min(f[j][k-1],f[j][k]+K);
}
}
rep(i,1,m)rep(j,1,m)
if(i!=j)ans=min(ans,f[i][j]);
cout<<ans<<endl;
return 0;
}
