Explorer Space题解

题目传送门

因为把路线一定可以转化成长方形，而长方形的边长一定是偶数，若

k

是偶数，发现若走

\displaystyle \frac{k}{2}

步时最优的，则剩下的

\displaystyle \frac{k}{2}

步肯定会选择原路返回，因为这样返回的路程也是最优的。所以问题转化成了在这个点走 $\displaystyle \frac{k}{2}$ 步最优需要的代价。所以我们用动态规划来做，用

dp_{i,j,k}

表示此点走

k

步最少代价，答案不要忘记翻倍，因为还有返回的代价。

AC Code：

CPP

#include<bits/stdc++.h>
using namespace std;
int n,m,g,dp[505][505][25],r[505][505],d[505][505];
int main(){
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	memset(dp,1e9+7,sizeof dp);
	cin>>n>>m>>g;
	if(g%2==1){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cout<<"-1 ";
			}
			cout<<"\n";
		}return 0;
	}
	for(int i=1;i<=n;i++) for(int j=1;j<m;j++) cin>>r[i][j];
	for(int i=1;i<n;i++) for(int j=1;j<=m;j++) cin>>d[i][j];
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) dp[i][j][0]=0;
	for(int k=1;k<=g/2;k++){
//		cout<<k<<":\n";
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(i>1) dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k-1]+d[i-1][j]);
				if(i<n) dp[i][j][k]=min(dp[i][j][k],dp[i+1][j][k-1]+d[i][j]);
				if(j>1) dp[i][j][k]=min(dp[i][j][k],dp[i][j-1][k-1]+r[i][j-1]);
				if(j<m) dp[i][j][k]=min(dp[i][j][k],dp[i][j+1][k-1]+r[i][j]);
//				cout<<dp[i][j][k]<<" ";
			}
//			cout<<"\n";
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cout<<dp[i][j][g/2]*2<<" ";
		}
		cout<<"\n";
	}
	return 0;
}

文章操作

题目传送门

AC Code：

相关推荐

评论

Explorer Space题解