洛谷 P1005 矩阵取数游戏

题目传送门

解题思路:

这道题说是矩阵,实际上每一行之间没联系,所以只需跑N此区间DP就行了.

f[i][j]表示从i~j能获得的最大分数.

本题唯一难度在于要写高精度,没有高精度感觉就是个黄题,本人做的第一道非模板的高精度题.

AC代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 
 5 using namespace std;
 6 
 7 int n,m,g[90];
 8 struct kkk{
 9     int s[999],len;
10     kkk() {
11         memset(s,0,sizeof(s));
12         len = 0;
13     }
14 }f[90][90],sum[90],ans;
15 
16 kkk operator * (const kkk &a,const int &b) {
17     kkk c;
18     c.len = a.len;
19     int x = 0;
20     for(int i = 1;i <= c.len; i++) {
21         c.s[i] = a.s[i] * b + x;
22         x = c.s[i] / 10;
23         c.s[i] %= 10;
24     }
25     while(x > 0) {
26         c.s[++c.len] = x % 10;
27         x /= 10;
28     }
29     return c;
30     
31 }
32 
33 kkk max(const kkk &a,const kkk &b) {
34     if(a.len > b.len) return a;
35     if(b.len > a.len) return b;
36     for(int i = a.len;i >= 1; i--) {
37         if(a.s[i] > b.s[i]) return a;
38         if(b.s[i] > a.s[i]) return b;
39     }
40     return a;
41 }
42 
43 kkk operator + (const kkk &a,const kkk &b) {
44     int u = max(a.len,b.len),x = 0;
45     kkk c;
46     for(int i = 1;i <= u; i++){
47         c.s[i] = a.s[i] + b.s[i] + x;
48         x = c.s[i] / 10;
49         c.s[i] = c.s[i] % 10;
50     }
51     if(x > 0)
52         c.s[++u] += x; 
53     c.len = u;
54     return c;
55 } 
56 
57 inline void wo() {
58     sum[0].len = 1;
59     sum[0].s[1] = 1;
60     for(int i = 1;i <= m + 2; i++)
61         sum[i] = sum[i-1] * 2;
62 }
63 
64 int main() {
65     scanf("%d%d",&n,&m);
66     wo();
67     while(n--) {
68         memset(f,0,sizeof(f));
69         for(int i = 1;i <= m; i++)
70             scanf("%d",&g[i]);
71         for(int i = 1;i <= m; i++)
72             for(int j = m;j >= i; j--) {
73                 f[i][j] = max(f[i][j],f[i-1][j] + sum[m-(j-i+1)] * g[i-1]);
74                 f[i][j] = max(f[i][j],f[i][j+1] + sum[m-(j-i+1)] * g[j+1]);
75             }
76         kkk a;
77         for(int i = 1;i <= m; i++)
78             a = max(a,f[i][i] + sum[m] * g[i]);
79         ans = ans + a;
80     }
81     for(int i = ans.len;i >= 1; i--)
82         printf("%d",ans.s[i]);
83     return 0;
84 }

//NOIP提高 2007 T3