我一定要认真读题
原题链接：75048.损友
2025-09-21 22:12:38
发布于：广东
14阅读
0回复
0点赞
赛时代码：
#include <iostream>
#include <cstdio>
#include <memory.h>
#define int long long
using namespace std;
int a[1005][1005];
int dp1[1005][1005], dp2[1005][1005];
int x[1000005], y[1000005];
int n, m, k, p;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m >> k >> p;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> a[i][j];
}
}
for(int i = 1; i <= k; i++){
cin >> x[i] >> y[i];
}
memset(dp1, 63, sizeof(dp1));
memset(dp2, 63, sizeof(dp2));
dp1[1][1] = a[1][1];
dp2[n][m] = a[n][m];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(i == 1 && j == 1) continue;
dp1[i][j] = min(dp1[i - 1][j], dp1[i][j - 1]) + a[i][j];
}
}
for(int i = n; i; i--){
for(int j = m; j; j--){
if(i == n && j == m) continue;
dp2[i][j] = min(dp2[i + 1][j], dp2[i][j + 1]) + a[i][j];
}
}
if(!k || !p){
cout << dp1[n][m];
return 0;
}
int mn1 = 0x3f3f3f3f3f3f3f3fll;
int mn2 = 0x3f3f3f3f3f3f3f3fll;
for(int i = 1; i <= k; i++){
mn1 = min(mn1, dp1[x[i]][y[i]]);
mn2 = min(mn2, dp2[x[i]][y[i]]);
}
cout << min(dp1[n][m], mn1 + mn2);
return 0;
}
AC 代码：
#include <iostream>
#include <cstdio>
#include <memory.h>
#define int long long
using namespace std;
int a[2005][2005];
int dp1[2005][2005], dp2[2005][2005];
int x[4000005], y[4000005];
int n, m, k, p;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m >> k >> p;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> a[i][j];
}
}
for(int i = 1; i <= k; i++){
cin >> x[i] >> y[i];
}
memset(dp1, 63, sizeof(dp1));
memset(dp2, 63, sizeof(dp2));
dp1[1][1] = a[1][1];
dp2[n][m] = a[n][m];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(i == 1 && j == 1) continue;
dp1[i][j] = min(dp1[i - 1][j], dp1[i][j - 1]) + a[i][j];
}
}
for(int i = n; i; i--){
for(int j = m; j; j--){
if(i == n && j == m) continue;
dp2[i][j] = min(dp2[i + 1][j], dp2[i][j + 1]) + a[i][j];
}
}
if(!k || !p){
cout << dp1[n][m];
return 0;
}
int mn1 = 0x3f3f3f3f3f3f3f3fll;
int mn2 = 0x3f3f3f3f3f3f3f3fll;
for(int i = 1; i <= k; i++){
mn1 = min(mn1, dp1[x[i]][y[i]]);
mn2 = min(mn2, dp2[x[i]][y[i]]);
}
cout << min(dp1[n][m], mn1 + mn2);
return 0;
}
有帮助，赞一个