P6649「SWTR-05」Grid 题解

题目链接 P6649「SWTR-05」Grid

分析

题意:

到了每一行第一个到的点时只能向左或者向上走，否则可以向右向左向上走，求经过所有格子的最小值。

思路

所以这道题可以使用动态规划来做

一开始开一个数组记录此点在可以往左走的情况下的最小值。

判断这个点可以从右到还是从下到的转移方程。因为要加上之前的值，所以转移方程我用了两个数组，一个记录值，一个存储原始值。

注意

记得开long long

转移方程是

f[i][j]=min(f[i+1][j],f[i][j+1])+a[i][j];
f[i][j]+=sum[i][j-1]-pp[i][j-1];

完整代码

#include <bits/stdc++.h>
using namespace std;
long long n,m,a[1001][1001],f[1005][1005],sum[1005][1005],pp[1005][1005],ans;
int main(void){
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        f[i][m+1]=1e9;
        for(int j=1;j<=m;++j){
            cin>>a[i][j];
            f[i][j]=1e9;
            sum[i][j]=sum[i][j-1]+a[i][j];
            pp[i][j]=max(pp[i][j-1],sum[i][j]);
        }
    }
    for(int i=n;i>=1;--i){
        for(int j=m;j>=1;--j){
            f[i][j]=min(f[i+1][j],f[i][j+1])+a[i][j];
        }
        for(int j=1;j<=m;++j){
            f[i][j]+=sum[i][j-1]-pp[i][j-1];
        }
    }
    ans=1e9;
    for(int i=1;i<=m;++i){
        ans=min(ans,f[1][i]);
    }
    cout<<ans;
    return 0;
}