#include<stdio.h> int map[11][11], dp[11][11]; int main() { int n, i, j, num = 0, res = 0; scanf("%d", &n); for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) { map[i][j] = 0; dp[i][j] = 0; } while (map[i][j] || i || j) { scanf("%d%d", &i, &j); scanf("%d", &map[i][j]); dp[i][j] = map[i][j]; } for (int i = 2; i <= n; i++) { dp[1][i] += dp[1][i - 1]; dp[i][1] += dp[i - 1][1]; } for (int i = 2; i <= n; i++) for (int j = 2; j <= n; j++) if (dp[i - 1][j] != 0 || dp[i][j - 1] != 0) if (dp[i - 1][j] > dp[i][j - 1]) dp[i][j] += dp[i - 1][j]; else dp[i][j] += dp[i][j - 1]; num += dp[n][n]; res = num; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (dp[i][j] == num) { if (map[i][j] + dp[i - 1][j] == num || map[i][j] + dp[i][j - 1] == num) { num -= map[i][j]; map[i][j] = 0; i = 1; j = 0; if (num == 0) break; } } } if (num == 0) break; } for (int i = 2; i <= n; i++) for (int j = 2; j <= n; j++) if (map[i - 1][j] != 0 || map[i][j - 1] != 0) if (map[i - 1][j] > map[i][j - 1]) map[i][j] += map[i - 1][j]; else map[i][j] += map[i][j - 1]; res += map[n][n]; printf("%d", res); return 0; }优化
时间: 2024-01-20 18:02:11 浏览: 51
可以将一些重复的代码封装成函数,以提高代码可读性和可维护性。例如,可以将计算最大价值和删除路径上某个点的操作封装成函数。
此外,可以使用更具有表达性的变量名,以便于理解代码含义。
下面是一个可能的优化版本:
```c
#include <stdio.h>
#define MAX_N 11
int map[MAX_N][MAX_N], dp[MAX_N][MAX_N];
int read_input(int n) {
int i, j;
while (scanf("%d%d", &i, &j) == 2) {
scanf("%d", &map[i][j]);
dp[i][j] = map[i][j];
}
return 0;
}
int compute_max_value(int n) {
int i, j;
for (i = 2; i <= n; i++) {
dp[1][i] += dp[1][i - 1];
dp[i][1] += dp[i - 1][1];
}
for (i = 2; i <= n; i++) {
for (j = 2; j <= n; j++) {
if (dp[i - 1][j] != 0 || dp[i][j - 1] != 0) {
dp[i][j] += dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];
}
}
}
return dp[n][n];
}
int delete_path(int n, int max_value) {
int i, j;
int current_value = max_value;
while (current_value > 0) {
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
if (dp[i][j] == current_value) {
if (map[i][j] + dp[i - 1][j] == current_value || map[i][j] + dp[i][j - 1] == current_value) {
current_value -= map[i][j];
map[i][j] = 0;
i = 1;
j = 0;
if (current_value == 0) {
return 0;
}
}
}
}
}
current_value--;
}
return 0;
}
int compute_max_path(int n) {
int i, j;
for (i = 2; i <= n; i++) {
for (j = 2; j <= n; j++) {
if (map[i - 1][j] != 0 || map[i][j - 1] != 0) {
map[i][j] += map[i - 1][j] > map[i][j - 1] ? map[i - 1][j] : map[i][j - 1];
}
}
}
return map[n][n];
}
int main() {
int n, max_value, max_path;
scanf("%d", &n);
read_input(n);
max_value = compute_max_value(n);
delete_path(n, max_value);
max_path = compute_max_path(n);
printf("%d", max_value + max_path);
return 0;
}
```
阅读全文