NOIP2007提高组.矩阵取数游戏

题目

492. 矩阵取数游戏

思路

不难发现, 每一行之间是独立的, 因此可以求出每一行的最大值, 然后行与行之间最大值相加, 就是总的最大值
对于行内来说, 每次可以选取左边或者右边, 可以使用区间$dp$求解, 时间复杂度$O(n^3)$, 因为列的最大值是$80$, 会超过$longlong$的最大范围, 可以使用__int128, 或者高精度加法处理结果

*被坑了, 计算$2^k$时也要转为$i128$

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>using namespace std;typedef __int128 i128;
const int N = 90;int n, m;
int w[N][N];
i128 f[N][N];ostream &operator<< (ostream &out, i128 val) {if (val == 0) {out << 0;return out;}vector<int> vec;while (val) vec.push_back(val % 10), val /= 10;while (!vec.empty()) out << vec.back(), vec.pop_back();return out;
}i128 solve(int w[]) {memset(f, 0, sizeof f);for (int len = 1; len <= m; ++len) {for (int i = 1; i + len - 1 <= m; ++i) {int j = i + len - 1;int cnt = m - j + i;if (len == 1) {f[i][j] = (i128) w[i] * (1 << cnt);continue;}f[i][j] = max(f[i + 1][j] + (i128) w[i] * (1 << cnt), f[i][j - 1] + (i128) w[j] * (1 << cnt));}}return f[1][m];
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {cin >> w[i][j];}}i128 res = 0;for (int i = 1; i <= n; ++i) res += solve(w[i]);cout << res << "\n";return 0;
}

$AC$代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>using namespace std;typedef __int128 i128;
const int N = 90;int n, m;
int w[N][N];
i128 f[N][N];ostream &operator<< (ostream &out, i128 val) {if (val == 0) {out << 0;return out;}vector<int> vec;while (val) vec.push_back(val % 10), val /= 10;while (!vec.empty()) out << vec.back(), vec.pop_back();return out;
}i128 solve(int w[]) {memset(f, 0, sizeof f);for (int len = 1; len <= m; ++len) {for (int i = 1; i + len - 1 <= m; ++i) {int j = i + len - 1;int cnt = m - j + i;if (len == 1) {f[i][j] = (i128) w[i] * ((i128) 1 << cnt);continue;}f[i][j] = max(f[i + 1][j] + (i128) w[i] * ((i128) 1 << cnt), f[i][j - 1] + (i128) w[j] * ((i128) 1 << cnt));}}return f[1][m];
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {cin >> w[i][j];}}i128 res = 0;for (int i = 1; i <= n; ++i) res += solve(w[i]);cout << res << "\n";return 0;
}