矩阵取数游戏

发表于 分类于

$Problem’s \ Website$

矩阵取数游戏

$Solution$

这道题可以用记忆化搜索，比较好理解，于是我就不说了。。。

我们来说一下$dp$的做法。

很明确，我们可以将每一行分开处理，而且处理的点只带两端，明显的区间$dp$。

我们设$f[i][j]$为当前区间变为$i,\ j$时的最大得分。

每次取数时，至于$i\ -\ 1$和$j\ +\ 1$有关，次数我们可以推出来为$m-j+i-1$

状态转移方程还是比较好推的。

对于每一行

$for\ i\ 1-m$

$for\ j\ m - i$

$ f[i][j]\ = \max(f[i - 1][j] + a[i - 1][j] \times 2^{n-j+i-1}, f[i][j+1]+a[i][j+1] \times 2^{n-j+i-1});$

最后只剩下一个数时

$f[i][i] = \max(f[i][i]+a[i][i] \times 2^m);$

对于每一行的$f[i][i]$取$\max$，最后答案为$\sum\limits_{i=1}^{n}{\max_{j=1}^{m}(f[j][j] + a[j][j] \times 2^m)}$

最后，温馨提示：本题要用高精度

$Code$

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define re register
const int Maxn = 90;
const int mod = 1e4;
struct BIG {
    int p[110];
    int len;
    BIG() {
        memset(p, 0, sizeof(p));
        len = 0;
    }
    void print() {
        printf("%d", p[len]);
        for(re int i = len - 1; i > 0; --i) {
            if(!p[i]) {
                printf("0000");
                continue;
            }
            for(re int k = 10; k * p[i] < mod; k *= 10)
                printf("0");
            printf("%d", p[i]);
        }
    }
    BIG operator + (const BIG &x) {
        BIG temp;
        int num = 0;
        temp.len = std :: max(len, x.len);
        for(re int i = 1; i <= temp.len; ++i) {
            temp.p[i] = p[i] + x.p[i] + num;
            num = temp.p[i] / mod;
            temp.p[i] %= mod;
        }
        while(num > 0) {
            temp.p[++temp.len] = num % mod;
            num /= mod;
        }
        return temp;
    }
    BIG operator * (int x) {
        BIG temp;
        int num = 0;
        temp.len = len;
        for(re int i = 1; i <= temp.len; ++i) {
            temp.p[i] = p[i] * x + num;
            num = temp.p[i] / mod;
            temp.p[i] %= mod;
        }
        while(num > 0) {
            temp.p[++temp.len] = num % mod;
            num /= mod;
        }
        return temp;
    }
}f[Maxn][Maxn], two[Maxn], ans;
BIG max (const BIG &x, const BIG &y) {
    if(x.len > y.len)
        return x;
    else if(x.len < y.len)
        return y;
    for(re int i = x.len; i > 0; --i) {
        if(x.p[i] > y.p[i])
            return x;
        else if(x.p[i] < y.p[i])
            return y;
    }
    return x;
}
int n, m;
inline void control() {
    two[0].p[1] = 1, two[0].len = 1;
    for(re int i = 1; i <= m + 1; ++i)
        two[i] = two[i - 1] * 2;
}
int a[Maxn];
int main() {
    scanf("%d%d", &n, &m);
    control();
    while(n--) {
        memset(f, 0, sizeof(f));
        for(re int i = 1; i <= m; ++i)
            scanf("%d", &a[i]);
        for(re int i = 1; i <= m; ++i)
            for(re int j = m; j >= i; --j) {
                f[i][j] = max(f[i][j], f[i - 1][j] + two[m - j + i - 1] * a[i - 1]);
                f[i][j] = max(f[i][j], f[i][j + 1] + two[m - j + i - 1] * a[j + 1]);
            }
        BIG temp;
        for(re int i = 1; i <= m; ++i)
            temp = max(temp, f[i][i] + two[m] * a[i]);
        ans = ans + temp;
    }
    ans.print();
    return 0;
}

$rp++$