Blowhard【省选模拟赛】

神仙优化DP

Posted by yjjr's blog on April 13, 2018

标签: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

时间复杂度

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;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr