（封面及头图Pixiv ID：111775584）


前言


最近一段时日，我一直在准备某学会组织的算法竞赛，在洛谷上做了不少（也不多哈哈哈）算法题。想着有些题目AC了就过去了，思路这些可能还是不太明晰，于是我心血来潮，打算写几篇题解总结总结。然而，题解数量太多的话太占位置，会把其他文章冲掉。因此我便做成集锦的形式，将所有题解合并成一篇文章，这样也极大方便了查阅。


题解按照题号从小到大排序，你可以点击目录或者使用浏览器的查找功能找到你想看的题解。


由于我水平有限，题解中所提到的解法可能并不是最优解法或最完美的解法。如果你有更好的方法，欢迎在评论区里提出或是联系我，大家一起交流学习，相互促进，共同成长！


因为目前我的时间较紧，本文的主要写作目的是为了总结做题过程，兼顾分享思路，因此讲解可能会有不够详细之处，还请见谅。当然，我会最大限度将我的解题思路讲清楚。如果你有不明白的地方，也可以在评论区提出或是联系我。

直达评论区

支持我


创作不易，请多支持。博客的运营需要时间、精力和金钱上的付出。如果你在阅读本博客的文章时有所收获，可以对本博客进行捐赠，以支持我的创作，激励我创作更加优质的内容！捐赠金额的大小无关情义，无论如何都非常感谢你们的支持和认可。当然，将你认为优质的文章转发出去，也算是一种支持！



联系我


欢迎读者们来与我一起交流探讨问题~


微信：ImOxygen233（一般全天候在线）


邮箱：konjac0629@outlook.com（时不时看一下）


P1005 [NOIP2007 提高组] 矩阵取数游戏


原题链接：Link




题目大意


有一个n×mn\times m的矩阵，矩阵中的每个元素ai,j (1≤i≤n,1≤j≤m)a_{i,j}\ (1\le i\le n,1\le j\le m)均为非负整数，现从中取数直至取完矩阵内所有元素，每次取数可取走各行的行首或行尾。

每次取数时还会有一个得分，对于第pp次取数，得分的计算公式为∑q=1naq,(1 or m+1−p)×2p\sum_{q=1}^{n} a_{q,(1\ \text{or}\ m+1-p)}\times 2^{p}，总得分即为这pp次取数的得分之和。现请你写一个程序，求出对于任意矩阵，完成取数后的最大总得分。


思路分析


不妨换个角度去理解题目中所描述的操作：


对于每一行，不断从行首或行尾取数，直至行为空。


我们可以把从行首取数或者从行尾取数视作是一次选择。做完一次选择后，在未取尽的情况下，还需要再做出一次选择。因此，很容易想到这是一道区间DP题。


对于每一行，我们可以把区间内元素数量大于1的区间视为大区间。对于每一个大区间，它的最大得分等于所作出的选择对应的得分与取走后得到的小区间的最大得分之和。可以先初始化元素数量为1的小区间的最大得分为2m2^{m}，因为取最后一个元素必然是在第mm次取，且不存在更小的区间了。接着不断扩展区间长度，推出元素数量为2,3,4...2,3,4...的区间的最大得分。当推至元素数量为mm的区间的最大得分时，我们便已经得到了该行的最大得分。


将所有行的最大得分相加，我们便可求出该矩阵完成取数后的最大得分。


状态转移方程：


dpj,k=max(matrixi,j×2m+j−k+dpj+1,k , matrixi,k×2m+j−k+dpj,k−1)\text{dp}_{j,k}=\text{max}(\text{matrix}_{i,j}\times 2^{m+j-k}+\text{dp}_{j+1,k}\ ,\ \text{matrix}_{i,k}\times 2^{m+j-k}+\text{dp}_{j,k-1})



其中 dpj,k\text{dp}_{j,k} 表示区间[j,k][j,k]的最大得分，matrixi,j\text{matrix}_{i,j} 表示矩阵第 i+1i+1 行第 j+1j+1 列的元素


由于本题的数据范围较大，你可能需要使用高精度和快速幂。在下面的参考代码中，我使用__int128_t来处理高精度整数




参考代码


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
98
99
100
101
102
103
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> matrix(0);
map<pair<int, int>, __int128_t> dp;
__int128_t ans;

__int128_t binpow(__int128_t a, __int128_t b) {
  __int128_t res = 1;
  while (b > 0) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}

/*
当然，也可以用迭代法转成string后输出
string int128ToString(__int128_t source)
{
    string result;
    if (source < 0)
    {
        result = "-" + result;
        source = -source;
    }
    char ch = source % 10 + '0';
    result = string(1, ch) + result;
    source /= 10;
    while (source > 0)
    {
        char ch = source % 10 + '0';
        result = string(1, ch) + result;
        source /= 10;
    }
    return result;
}
*/

void int128Print(__int128_t source)
{
    if (source < 0)
    {
        putchar('-');
        source = -source;
    }
    if (source >= 10)
        int128Print(source / 10);
    putchar(source % 10 + '0');
}

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        vector<int> tempV(0);
        for (int j = 0; j < m; j++)
        {
            int tempN;
            cin >> tempN;
            tempV.push_back(tempN);
        }
        matrix.push_back(tempV);
    }
    for (int i = 0; i < n; i++)
    {
        for (int len = 0; len < m; len++)
        {
            for (int j = 0, k = len; j < m && k < m; j++, k = j + len)
            {

                if (j == k)
                {
                    dp[{j, k}] = matrix[i][j] * binpow(2, m);
                    /*
                    调试用
                    cout << "dp[{" << j << "," << k << "}]: " << (long long)dp[{j, k}] << endl;
                    */
                }
                else
                {
                    dp[{j, k}] = max(dp[{j + 1, k}] + matrix[i][j] * binpow(2, m + j - k), dp[{j, k - 1}] + matrix[i][k] * binpow(2, m + j - k));
                    /*
                    调试用
                    cout << "dp[{" << j << "," << k << "}]: " << (long long)dp[{j, k}] << endl;
                    */
                }
            }
        }
        ans += dp[{0, m - 1}];
        dp.clear();
    }
    int128Print(ans);
    /*
    用迭代法转成string后再输出的话
    cout << int128ToString(ans) << endl;
    */
    return 0;
}