z3475 的博客

题解 P1004 【方格取数】

大家都知道走一次的动态转移方程是

f[x][y]=max(f[x-1][y],f[x][y-1])+a[x][y];

那走俩次我们可以把数组加个俩维,代表第一次最大值+第二次的最大值,那方程就变成了这个

f[x1][y1][x2][y2]=max(

f[x1-1][y1][x2-1][y2],

f[x1-1][y1][x2][y2-1],

f[x1][y1-1][x2-1][y2],

f[x1][y1-1][x2][y2-1])+a[x1][y1]+a[x2][y2];

但是按照这个方程来看,明显f[n][n][n][n]=max(...)+2a[n][n]; 所以当x1==x2&&y1==y2时只要加一次

#include <bits/stdc++.h>

using namespace std;
int a[10][10];
int f[10][10][10][10];//记忆化
int max(int a,int b,int c,int d){
    return max(max(max(a,b),c),d);
}
int po(int x1,int y1,int x2,int y2){
    if (f[x1][y1][x2][y2]!=-1) return f[x1][y1][x2][y2];

    if (x1<=0||y1<=0||x2<=0||y2<=0) return 0;

    register int add;
    if (x1==x2&&y1==y2) add=a[x1][y1];
    else add=a[x1][y1]+a[x2][y2];

    return f[x1][y1][x2][y2]=max(
    po(x1-1,y1,x2-1,y2),
    po(x1-1,y1,x2,y2-1),
    po(x1,y1-1,x2-1,y2),
    po(x1,y1-1,x2,y2-1)
    )+add;
}

int main(){
    memset(f,-1,sizeof(f));
    int n;scanf("%d",&n);
    int q,w,e;scanf("%d%d%d",&q,&w,&e);
    do{
        a[q][w]=e;
        scanf("%d%d%d",&q,&w,&e);
    }while(!(q==0&&w==0&&e==0));
    printf("%d",po(n,n,n,n));
}

2018-02-17 15:50:57 in 未分类