四维dp,20pts。debug许久无果……
查看原帖
四维dp,20pts。debug许久无果……
338786
mushroom_knight楼主2020/7/18 20:19

RT:

#include<bits/stdc++.h>
#define in(i) scanf("%llu",&i);
#define out(i) printf("%llu",i);
using namespace std;
typedef unsigned long long ull;
ull f[55][55][55][55];
ull m,n;
ull a[55][55];

ull max_ull(ull a,ull b,ull c,ull d){
	if(b>a){
		a=b;
	}
    if(c>a){
    	a=c;
    }  
    if(d>a){
    	a=d;
    }        
    return a;
}

/*void debug(int i,int j,int k,int l){
     printf("f[%d][%d][%d][%d]=%d\n",i,j,k,l,f[i][j][k][l]);
}*/

int main(){
	in(m);
	in(n);
	for(register ull i=1;i<=m;++i){
		for(register ull j=1;j<=n;++j){
			in(a[i][j]);
		}
	}
	for(register ull i=1;i<=m;++i){
		for(register ull j=1;j<=n;++j){
			for(register ull k=1;k<=m;++k){
				for(register ull l=j+1;l<=n;++l){
					f[i][j][k][l]=max_ull(f[i-1][j][k-1][l],f[i][j-1][k][l-1],f[i][j-1][k-1][l],f[i][j][k-1][l-1])+(a[i][j]+a[k][l]);
					//debug(i,j,k,l); 
				}
			}
		}
    }
	out(f[m][n-1][m-1][n]);
	puts("");
	return 0;
}


2020/7/18 20:19
加载中...