Explorer Space题解

__DAN__ · 2024-12-13 16:17:12 · 题解

题目传送门

因为把路线一定可以转化成长方形，而长方形的边长一定是偶数，若 k 是偶数，发现若走 \displaystyle \frac{k}{2} 步时最优的，则剩下的 \displaystyle \frac{k}{2} 步肯定会选择原路返回，因为这样返回的路程也是最优的。所以问题转化成了在这个点走 \displaystyle \frac{k}{2} 步最优需要的代价。所以我们用动态规划来做，用 dp_{i,j,k} 表示此点走 k 步最少代价，答案不要忘记翻倍，因为还有返回的代价。

AC Code：

#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;
}