题解：P1005 [NOIP 2007 提高组] 矩阵取数游戏

· · 题解

一道考试中的题，来写篇题解。

我们首先发现每行是独立的，于是可以一行一行的处理。

又发现贪心有后效性，遂准备 dp。

对于每行，设 dp_{l,r} 为除了区间 [l,r]，其它数都取完的最大得分。

所以这一行的最大得分为 \max_{1\le x\le m}dp_{x,x-1}。

转移也很好想了，设 s=r-l+1，a 数组为该行的数字。

dp_{l,r}=\max(dp_{l-1,r}+a_{l-1}\times 2^{n-s},dp_{l,r+1}+a_{r+1}\times 2^{n-s})

此式转移一个是取左边一个是取右边，所以显然成立。

最后就是注意 dp 的转移顺序了，还有要开 __int128。

一道水绿就这样的切了。

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[110];
__int128 dp[110][110];
__int128 sum=0;
void write(__int128 x){
    if(x>=10) write(x/10);
    putchar(x%10+'0');
}
int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) cin>>a[j];
        dp[1][m]=0;
        for(int j=1;j<=m;j++)
            for(int k=m;k>=j-1;k--)
                dp[j][k]=max(dp[j-1][k]+a[j-1]*(__int128(1)<<(j-1+m-k)),dp[j][k+1]+a[k+1]*(__int128(1)<<(j-1+m-k)));
        __int128 ans=0;
        for(int j=1;j<=m;j++) ans=max(ans,dp[j][j-1]);
        sum+=ans;
    }
    write(sum);
    return 0;
}