P1005 [NOIP2007 提高组] 矩阵取数游戏 题解(区间dp)

题目链接

题目思路

每行都是独立的

然后只能从开头和结尾取，显然就是区间dp

然后注意__int128输出是0特判

代码

#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const int maxn=80+5,mod=1e9+7;
int n,m;
int a[maxn][maxn];
ll dp[maxn][maxn][maxn];
ll base[maxn];
void pr(ll ans){
	if(ans==0) return ;
	pr(ans/10);
	printf("%d",(int)(ans%10));	
}
int main(){
    base[0]=1;
    for(int i=1;i<=80;i++){
        base[i]=base[i-1]*2;
    }
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        for(int r=1;r<=m;r++){
            for(int l=r;l>=1;l--){
                int pow=m-(r-l);
                dp[i][l][r]=max(dp[i][l+1][r]+a[i][l]*base[pow],dp[i][l][r-1]+a[i][r]*base[pow]);
            }
        }
        ans+=dp[i][1][m];
    }
    if(ans==0){// 特判 
    	printf("0
");
	}else{
		pr(ans); 
	}
	return 0;
}