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

· · 题解

我们可以发现，这个矩阵的每行都是独立的，于是我们可以分别计算每一行的最大得分。

考虑区间 DP。

对于每一行，我们设 f_{l,r} 表示将 [l,r] 取完后，所获得的最大得分。

因为每次只能取行首或行尾，所以我们可以推出状态转移方程：

f_{l,r} = \max (f_{l,r-1} + 2^{n - len + 1} \times a_r , f_{l+1,r} + 2^{n-len+1} \times a_l)

总时间复杂度：O(nm^2)。

要注意本题需要开__int128。

代码：


#include<cstdio>
#define max(a,b) (a>b?a:b)
using namespace std;
const int N=90,mod=2,mod10=10;
__int128 f[N][N],v[N],ans;
__int128 power(__int128 a,__int128 b){
    __int128 ans=1;
    while(b){
        if(b%mod) ans=ans*a;
        b/=mod;
        a=a*a;
    }
    return ans;
}
__int128 read(){
    __int128 x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+(c^48);
        c=getchar();
    }
    return x*f;
}
void write(__int128 x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}
int main(){
    int m,n;//这里的 n 和 m 与原题相反
    scanf("%d%d",&m,&n);
    while(m--){
        for(int i=1;i<=n;i++){
            v[i]=read();
            f[i][i]=power(2,n)*v[i];
        }
        for(int len=2;len<=n;len++){
            for(int i=1;i+len-1<=n;i++){
                int j=i+len-1;
                f[i][j]=max(f[i][j-1]+power(2,n-len+1)*v[j],f[i+1][j]+power(2,n-len+1)*v[i]);
            }
        }
        ans+=f[1][n];
    }
    write(ans);
    return 0;
}