Luogu7074 [CSP-J2020] 方格取数(dp)题解

发布于 2020-12-21  343 次阅读


食用前提示:本文搬自作者的洛谷博客。

题面:

$n \times m$ 的网格图,要从图的左上角走到右下角,每个格子有一个值 $a_i$(可以是负数), 每一步只能向上、向下或向右走一格,并且不能重复经过已经走过的方格,求走过的格子的整数之和的最大值。

$1 \le n,m \le 10^3$,$1 \le |a_i|\le 10^4$

思路:

很明显的dp,一看 $n,m \le 10^3$ 可以确定是二维。然后看到题目说只能向上向下向右走,看出把一列看成一个整体,做一个前缀和,应该可以优化到后面的DP。

不难想到一个 $O(n^2m)$ 的70分DP,设 $dp_{i,j}$ 表示在第 $i$ 列第 $j$ 行时候的值,转移方程就是枚举 $1\le j \le n$ , $1 \le k \le n$ 暴力转移,加上 $a_{i+1,j}$ $a_{i+1,k}$ 的和即可。

然后考虑优化。设 $dp_{i,j}$ 表示在第 $i$ 列第 $j$ 行并且要到下一列时可以取到的最大数值。为什么这么设呢?我们可以发现,在任何一个位置开始都可以向上/向下走到当前位置,而到达当前位置以后就直接向右走到下一列,是与如何过来无关的,我们只要关心那个最大值就可以了。所以开两个 $dp$ 数组储存一下从下面/上面走过来的最大值就好了。思路不难,但是很考验选手的灵性(比如我这种老年选手在考场上就$70pts$滚粗了)。

PS:十年OI一场空,不开long long__________

代码(70pts):

//注意开long long!(10^6*10^4) 
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
const long long inf=100000000000000005;

int n,m;
long long a[N][N],f[N][N];

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

inline long long GetMax(long long x,long long y){
    if (x>y) return x;
    else return y;
}

inline long long GetDis(int line,int x,int y){
    if (x>y) return a[x][line]-a[y-1][line];
    else return a[y][line]-a[x-1][line];
}

void sub_task1(){
    //设f[i][j]表示当前在第i列第j行的最大值
    for (int i=1;i<=m;i++)
        for (int j=1;j<=n;j++)
            f[i][j]=-inf;
    for (int i=1;i<=n;i++) f[1][i]=GetDis(1,1,i);
    for (int i=1;i<=m-1;i++){
        for (int k=1;k<=n;k++)
            for (int j=1;j<=n;j++)
                f[i+1][k]=GetMax(f[i+1][k],f[i][j]+GetDis(i+1,j,k));
    }
//  for (int i=1;i<=n;i++){
//      for (int j=1;j<=m;j++)
//          printf("%lld ",f[j][i]);
//      printf("\n");
//  }
    printf("%lld\n",f[m][n]);
}

void sub_task2(){
    //设f[i][j]表示当前在第i列第j行的最大值
    for (int i=1;i<=m;i++)
        for (int j=1;j<=n;j++)
            f[i][j]=-inf;
    for (int i=1;i<=n;i++) f[1][i]=GetDis(1,1,i);
    for (int i=1;i<=m-1;i++){
        for (int k=1;k<=n;k++)
            for (int j=1;j<=n;j++)
                f[i+1][k]=GetMax(f[i+1][k],f[i][j]+GetDis(i+1,j,k));
    }
//  for (int i=1;i<=n;i++){
//      for (int j=1;j<=m;j++)
//          printf("%lld ",f[j][i]);
//      printf("\n");
//  }
    printf("%lld\n",f[m][n]);
}

int main(){
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    n=read(),m=read();
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            a[i][j]=read()+a[i-1][j];       //前缀和优化
    if (n<=300) sub_task1();
    else sub_task2();
    return 0;
}

代码(100pts):

//注意开long long!(10^6*10^4) 
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
const long long inf=100000000000000005;

int n,m;
long long a[N][N],f[N][N],dp1[N],dp2[N];

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

//inline long long GetMax(long long x,long long y){
//  if (x>y) return x;
//  else return y;
//}
//
//inline long long GetDis(int line,int x,int y){
//  if (x>y) return a[x][line]-a[y-1][line];
//  else return a[y][line]-a[x-1][line];
//}
//
//void sub_task1(){
//  //设f[i][j]表示当前在第i列第j行的最大值
//  for (int i=1;i<=m;i++)
//      for (int j=1;j<=n;j++)
//          f[i][j]=-inf;
//  for (int i=1;i<=n;i++) f[1][i]=GetDis(1,1,i);
//  for (int i=1;i<=m-1;i++){
//      for (int k=1;k<=n;k++)
//          for (int j=1;j<=n;j++)
//              f[i+1][k]=GetMax(f[i+1][k],f[i][j]+GetDis(i+1,j,k));
//  }
////    for (int i=1;i<=n;i++){
////        for (int j=1;j<=m;j++)
////            printf("%lld ",f[j][i]);
////        printf("\n");
////    }
//  printf("%lld\n",f[m][n]);
//}

void sub_task2(){
    f[1][1]=a[1][1];
    for (int i=2;i<=n;i++)
        f[i][1]=f[i-1][1]+a[i][1];
    for (int j=2;j<=m;j++){
        dp1[1]=f[1][j-1]+a[1][j];
        dp2[n]=f[n][j-1]+a[n][j];
        for (int i=2;i<=n;i++)
            dp1[i]=max(dp1[i-1],f[i][j-1])+a[i][j];
        for (int i=n-1;i;i--) 
            dp2[i]=max(dp2[i+1],f[i][j-1])+a[i][j];
        for (int i=1;i<=n;i++)
            f[i][j]=max(dp1[i],dp2[i]);
    }
    printf("%lld\n",f[n][m]);
}

int main(){
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    n=read(),m=read();
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            a[i][j]=read();
    sub_task2();
    return 0;
}

都看到这里了不点个赞么TAT。。


我们无法选择过去,但我们可以改变未来。