【NOIP2007】【Vijos1378】矩阵取数游戏

problem

solution

codes

//每行独立区间DP, 贪心反例->某行像这样，4 1 1 1 1 1 233 3 3
//2^80数据, 所以记得高精.
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;
typedef long long LL;
typedef __int128 LLL;
const int maxn = 110;
int n, m, a[maxn];
LLL t[maxn], f[maxn][maxn], _max, ans;
void print(LLL ans){
    if(ans == 0)return ;
    else print(ans/10);
    putchar(ans%10+'0');
}
int main(){
    cin>>n>>m;
    t[0] = 1;
    for(int i = 1; i <= m; i++)t[i] = t[i-1]*2;
    while(n--){
        for(int i = 1; i <= m; i++)cin>>a[i];
        memset(f, 0, sizeof f);
        //for(int i = 1; i <= m; i++)f[i][i] = t[m]*a[i];//边界条件
        //f[i][j]:这行还剩下[i,j]时能得到的最高分
        //转移加上分别取了左边的和右边的数的时候的得分
        for(int i = 1; i <= m; i++)
            for(int j = m; j >= i; j--)
                f[i][j]=max(f[i-1][j]+t[m-(j-i+1)]*a[i-1], f[i][j+1]+t[m-(j-i+1)]*a[j+1]);
        //枚举最后一个取的是哪个数，得到这一行的最高分
        _max = 0;
        for(int i = 1; i <= m; i++)_max = max(_max, f[i][i]+t[m]*a[i]);
        ans += _max;
    }
    if(ans == 0)cout<<"0\n";
    else print(ans);
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80404284