c++ noi 方格取数

以下是一个使用动态规划解决方格取数问题的 C++ 代码示例： ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; // 输入方格的大小 vector<vector<int>> grid(n, vector<int>(n)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> grid[i][j]; // 输入每个格子的整数值 } } vector<vector<int>> dp(n, vector<int>(n)); dp[0][0] = grid[0][0]; // 计算第一行的最大路径和 for (int j = 1; j < n; j++) { dp[0][j] = dp[0][j-1] + grid[0][j]; } // 计算第一列的最大路径和 for (int i = 1; i < n; i++) { dp[i][0] = dp[i-1][0] + grid[i][0]; } // 计算其他格子的最大路径和 for (int i = 1; i < n; i++) { for (int j = 1; j < n; j++) { dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]; } } cout << dp[n-1][n-1] << endl; // 输出最大路径和 return 0; } ``` 在这个代码中，我们首先读取方格的大小以及每个格子的整数值。然后，使用一个二维数组 `dp` 来存储最大路径和。通过动态规划的思想，我们先计算第一行和第一列的最大路径和，然后逐步计算其他格子的最大路径和。最后，输出 `dp[n-1][n-1]` 即为所求的最大路径和。 希望这段代码对你有所帮助！如有任何疑问，请随时提问。

### NOI 2013 矩阵取数游戏 解题报告 #### 背景描述 题目涉及两个玩家轮流在一个 \(s \times n\) 的矩阵中选取元素，目标是在若干轮操作之后使得最终得分最大。每个位置上的数值会随着被选择次数增加而翻倍。 #### 动态规划建模 为了有效解决这个问题，可以构建动态规划模型来追踪当前状态下可能获得的最大分数。定义状态转移方程如下： \[ dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + matrix[i][j]*2^{(i+j)} \] 这里 `dp[i][j]` 表示到达第 i 行 j 列时能够得到的最大总分；\(matrix[i][j]\) 是原始输入矩阵中的值；指数部分代表该格子被访问过的次数[^5]。 #### 循环节优化 考虑到直接计算上述 DP 方案的时间复杂度较高，在实际实现过程中可以通过观察到的循环特性来进行加速。具体来说，如果存在某个时刻某项满足条件 \(num \% k == 1\) ，则意味着这一序列已经形成了完整的周期模式[^3]。利用这一点可以在一定程度上减少不必要的重复运算。 #### 实现细节 基于以上分析，下面给出 Python 版本的核心算法框架： ```python MOD = 1_000_000_007 def solve(matrix, rows, cols): # 初始化DP表 dp = [[0]*(cols+1) for _ in range(rows+1)] # 计算每一层的结果并更新至DP表内 for r in range(1, rows + 1): for c in range(1, cols + 1): power = pow(2, (r+c)-2, MOD) value = matrix[r-1][c-1] dp[r][c] = ((max(dp[r-1][c], dp[r][c-1])) % MOD + (value * power)) % MOD return dp[-1][-1] # 示例调用 if __name__ == "__main__": from sys import stdin input_data = list(map(int, stdin.read().strip().split())) row_count, col_count = input_data[:2] values = input_data[2:] game_matrix = [] index = 0 for _ in range(row_count): temp_row = [values[index+i] for i in range(col_count)] game_matrix.append(temp_row) index += col_count result = solve(game_matrix, row_count, col_count) print(result) ``` 此代码片段实现了基本的动态规划求解过程，并考虑到了大整数溢出的情况通过取模运算加以规避。