[NOIp2007提高组]矩阵取数游戏

OJ题号：洛谷1005

思路：

动态规划。

不难发现每行能够取得的最大值仅与当前行的数据有关，因此本题可以对每行的数据分别DP，最后求和。

设$f_{i,j}$表示左边取$i$个、右边取$j$个的最大值，则DP方程为$f_{i,j}=max(f_{i-1,j}+a_{i-1}*2^{i+j},f_{i,j-1}+a_{m-j}*2^{i+j})$。

然而数据规模较大，使用 int 只有40分，用 unsigned long long 只有60分。所以需要高精度，不过实现起来并不复杂。

另外有一些小小的优化，比如压位、预处理二的幂。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 class BigInt {
 5     private:
 6         static const int k=10000;
 7         int num[100],len;
 8     public:
 9         BigInt() {
10             memset(num,0,sizeof num);
11             len=0;
12         }
13         BigInt(const int len,const int num) {
14             this->len=len;
15             this->num[0]=num;
16         }
17         BigInt operator + (const BigInt &x) const {
18             BigInt ans;
19             for(int i=0;i<=(ans.len=std::max(this->len,x.len));i++) {
20                 ans.num[i]+=this->num[i]+x.num[i];
21                 ans.num[i+1]=ans.num[i]/k;
22                 ans.num[i]%=k;
23             }
24             if(ans.num[ans.len+1]) ans.len++;
25             return ans;
26         }
27         BigInt operator * (const int &x) const {
28             BigInt ans;
29             for(int i=0;i<=(ans.len=this->len);i++) {
30                 ans.num[i]+=this->num[i]*x;
31                 ans.num[i+1]=ans.num[i]/k;
32                 ans.num[i]%=k;
33             }
34             if(ans.num[ans.len+1]) ans.len++;
35             return ans;
36         }
37         bool operator < (const BigInt &x) const {
38             if(this->len<x.len) return true;
39             if(this->len>x.len) return false;
40             for(int i=this->len;i>=0;i--) {
41                 if(this->num[i]<x.num[i]) return true;
42                 if(this->num[i]>x.num[i]) return false;
43             }
44             return false;
45         }
46         BigInt& operator = (const BigInt &x) {
47             this->len=x.len;
48             std::copy(&x.num[0],&x.num[len+1],this->num);
49             return *this;
50         }
51         void print() {
52             printf("%d",num[len]);
53             for(int i=len-1;i>=0;i--) {
54                 printf("%04d",num[i]);
55             }
56             printf("
");
57         }
58 };
59 const int M=81;
60 BigInt pow[M]={BigInt(0,1)};
61 void calcpow(const int x) {
62     pow[x]=pow[x-1]*2;
63 }
64 int main() {
65     int n,m;
66     scanf("%d%d",&n,&m);
67     for(int i=1;i<=m;i++) calcpow(i);
68     BigInt ans;
69     while(n--) {
70         int a[m];
71         BigInt f[m+1][m+1];
72         for(int i=0;i<m;i++) scanf("%d",&a[i]);
73         memset(f,0,sizeof f);
74         BigInt max;
75         for(int i=0;i<=m;i++) {
76             for(int j=0;j<=m-i;j++) {
77                 if(i) f[i][j]=std::max(f[i][j],f[i-1][j]+pow[i+j]*a[i-1]);
78                 if(j) f[i][j]=std::max(f[i][j],f[i][j-1]+pow[i+j]*a[m-j]);
79             }
80             max=std::max(max,f[i][m-i]);
81         }
82         ans=ans+max;
83     }
84     ans.print();
85     return 0;
86 }