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

知识点

区间动态规划、大整数、最优策略

解题思路

各行之间没有选择约束，可以独立求最优后相加。对一行，f[l][r]表示已取走区间外元素后，剩余[l,r]能获得的最大分数。当前是第m-(r-l+1)+1次取数，枚举取左端或右端，分别加上端点值乘2的当前次数次幂。长度从小到大计算。使用__int128并自行输出十进制。

正确性说明

任意合法方案第一步只能取左或右，之后剩下连续子区间，故两种转移穷尽全部选择。取数权重由已取元素数唯一决定，满足最优子结构。所有行完全独立，逐行最优和就是总最优。上界小于80·1000·2^81，远低于有符号128位上限。

易错点

第一次权重是2而非1；不能用long long；每行分别优化；全零仍应输出0。

复杂度

时间O(nm²)，空间O(m²)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
using I=__int128_t;void print(I x){if(x>=10)print(x/10);cout<<char('0'+x%10);}int main(){int n,m;cin>>n>>m;I ans=0,p[82];p[0]=1;for(int i=1;i<=m;i++)p[i]=p[i-1]*2;while(n--){vector<int>a(m+2);for(int i=1;i<=m;i++)cin>>a[i];vector<vector<I>>f(m+2,vector<I>(m+2));for(int len=1;len<=m;len++)for(int l=1;l+len-1<=m;l++){int r=l+len-1,k=m-len+1;f[l][r]=max(f[l+1][r]+a[l]*p[k],f[l][r-1]+a[r]*p[k]);}ans+=f[1][m];}print(ans);cout<<'\n';}