一天白雪公主来到超市为777个小矮人买鸡蛋,这里的鸡蛋都包装在一个R行C列的二维表格里,每个格子的鸡蛋数都不相同。白雪公主从表格左上角出发,每次只能向下或者向右走一格,一直走到右下角。途中经过的每个格子,白雪公主就会把该格子的鸡蛋取走。 最后白雪公主把取到的所有鸡蛋,除以777,她希望这个余数最大。你能帮她计算最大的余数是多少吗? 输入格式 输入文件名:egg.in 第一行,R和C。 1 <=R ,C <= 50。 接下来是R行C列的表格,第i行第j列的整数表示该格子的鸡蛋数量,范围是[1,1000]。 输出格式 输出文件名:egg.out 一个整数。表示最大的余数。 输入/输出例子1 输入: 3 3 537 522 263 721 81 377 161 234 478 输出: 640
时间: 2024-04-17 11:28:54 浏览: 172
这是一个典型的动态规划问题,可以使用动态规划算法来解决。下面是一个C++实现的示例代码:
```cpp
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ifstream input("egg.in");
ofstream output("egg.out");
int R, C;
input >> R >> C;
vector<vector<int>> grid(R, vector<int>(C));
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
input >> grid[i][j];
}
}
vector<vector<int>> dp(R, vector<int>(C, 0));
dp[0][0] = grid[0][0];
for (int i = 1; i < R; i++) {
dp[i][0] = (dp[i-1][0] + grid[i][0]) % 777;
}
for (int j = 1; j < C; j++) {
dp[0][j] = (dp[0][j-1] + grid[0][j]) % 777;
}
for (int i = 1; i < R; i++) {
for (int j = 1; j < C; j++) {
dp[i][j] = (max(dp[i-1][j], dp[i][j-1]) + grid[i][j]) % 777;
}
}
output << dp[R-1][C-1] << endl;
input.close();
output.close();
return 0;
}
```
你可以将输入数据保存到名为`egg.in`的文件中,然后运行这段代码得到输出结果,结果将保存在名为`egg.out`的文件中。
希望这个示例代码能帮助到你,如果有任何疑问,请随时提问。
阅读全文