洛谷P1005 矩阵取数游戏问题,只过了四个ac,
矩阵取数游戏问题,只过了4个ac,希望大牛能指点下
状态转移方程: f[i][j]=max(f[i+1][j]2+f[i][i], f[i][j-1]2+f[j][j])
状态初始化: f[i][i] = line * 2
代码:
using namespace std; const int MAX_N = 81; __int128 max_Num, lastNum, result; __int128 dp[MAX_N][MAX_N]; int line[MAX_N]; inline void print(__int128 x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9) print(x / 10); putchar(x % 10 + '0'); } inline __int128 read(int i) { __int128 x = 0, sign = 1; string str = to_string(i); for (char ch : str) { if ('0' > ch || ch > '9') { if (ch == '-') sign = -1; } if (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; } } return x * sign; } inline __int128 getDpNum(int start, int end) { for (int i = 1; i <= end; ++i) { dp[i][i] = read(line[i] * 2); } for (int i = end - 1; i > 0; --i) { for (int j = i + 1; j <= end; ++j) { if (dp[i][j - 1] > dp[i + 1][j]) { max_Num = dp[i][j - 1]; lastNum = dp[j][j]; } else { max_Num = dp[i + 1][j]; lastNum = dp[i][i]; } dp[i][j] = max_Num *2+lastNum; } } return dp[1][end]; } int main() { int row, column; cin >> row >> column; for (int i = 1; i <= row; ++i) { // 依次输入每行 for (int j = 1; j <= column; ++j) { cin >> line[j]; } // 通过dp获取每行的最大值 result+=getDpNum(1, column); } print(result); cout << endl; return 0; }