谁能帮我看看我的代码Bug
2026-07-30 19:40:19
发布于：广东
T125628.异星矿区
普及+/提高
加入题单
通过率：
17.89%
时间限制：
1.00s
内存限制：
128MB
题目描述
输入文件：y.in
输出文件：y.out
题目背景
在遥远的异星，有一片巨大的网格状矿区，里面蕴藏着丰富的能量矿石。
题目描述
矿区可以看作是一个 N 行 M 列的二维矩阵。位于第 i 行第 j 列的区域中，有价值为 w
i,j
的能量矿石。
一辆探测车从矿区的左上角 (1,1) 出发，目标是到达右下角 (N,M)。探测车每次只能向 右 移动一格或向 下 移动一格。每进入一个格子（包括起点和终点），探测车就会收集该格子里的所有能量矿石。
然而，异星的环境非常极端。如果探测车在同一个方向上连续行驶的步数超过了 K 步，其引擎就会过热爆炸。也就是说：
探测车不能连续向下移动超过 K 次。
探测车不能连续向右移动超过 K 次。
请你计算出，探测车在安全到达终点 (N,M) 的前提下，最多能收集到多少总价值的能量矿石？如果无论如何探测车都无法安全到达终点，请输出 -1。
输入格式
第一行包含三个整数 N,M,K，分别表示矩阵的行数、列数以及连续移动步数的上限。
接下来的 N 行，每行包含 M 个整数。其中第 i 行的第 j 个整数表示 w
i,j
。
输出格式
输出共 1 行，包含一个整数，表示最多能收集的矿石总价值；若无法到达终点，输出 -1。
输入输出样例
输入#1
2 3 2
1 2 3
4 5 6
输出#1
16
输入#2
1 5 2
1 2 3 4 5
输出#2
-1
说明/提示
说明/提示
【样例解释 1】
一种最优的移动路径是：
(1,1)→(2,1)→(2,2)→(2,3)。
该路径的移动指令为：下、右、右。
连续方向统计如下：
第一次 向下 行驶 1 步（到达 2,1）
第一次 向右 行驶 2 步（到达 2,3）
在整个过程中，没有任何同向连续移动超过 K=2 步，路径合法。
总价值为 1+4+5+6=16。
【数据范围】
本题共有 5 个子任务。具体限制与约定如下表所示：
子任务编号 分值 限制与特殊性质
1 10 K≥max(N,M)
2 20 N,M≤10
3 20 K=1
4 30 N,M≤100
5 20 无特殊限制
对于 100% 的数据，有 1≤N,M≤500，1≤K≤10，0≤w
我的代码
#include<bits/stdc++.h>
using namespace std;
long long n,m,k,a[505][505],dp[505][505][2][11],vis[505][505];
int main(){
freopen("y.in","r",stdin);
freopen("y.out","w",stdout);
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
long long ny=j-1,nx=i-1,qy=m-j,qx=n-i;
if((ny+1)*k>=nx&&(nx+1)*k>=ny&&(qy+1)*k>=qx&&(qx+1)*k>=qy){
vis[i][j]=1;
}
else{
vis[i][j]=0;
}
}
}
if(vis[n][m]==0){
cout<<-1;
return 0;
}
dp[1][1][0][0]=dp[1][1][1][0]=a[1][1];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int z=0;z<=1;z++){
for(int w=0;w<=k;w++){
long long ma=0;
if(i==1&&j==1) continue;
if(z==0){
if(w==1){
for(int f=0;f<=k;f++){
ma=max(ma,dp[i-1][j][1][f]);
}
}
else ma=max(ma,dp[i-1][j][0][w-1]);
}
else{
if(w==1){
for(int f=0;f<=k;f++){
ma=max(ma,dp[i][j-1][0][f]);
}
}
else ma=max(ma,dp[i][j-1][1][w-1]);
}
dp[i][j][z][w]=ma;
dp[i][j][z][w]+=a[i][j];
}
}
}
}
long long ma=0;
for(int z=0;z<=1;z++){
for(int w=1;w<=k;w++){
ma=max(dp[n][m][z][w],ma);
}
}
cout<<ma;
fclose(stdin);
fclose(stdout);
return 0;
}
全部评论 1
#include <bits/stdc++.h> #define ll long long using namespace std; const ll N=5e2+10; ll a[N][N],n,m,k,dp[N][N][2][11],ans; int main(){ freopen("y.in","r",stdin); freopen("y.out","w",stdout); cin>>n>>m>>k; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; } } memset(dp,-1,sizeof(dp)); dp[1][1][1][0]=dp[1][1][0][0]=a[1][1]; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(i==1&&j==1) continue; for(int c=1;c<=k;c++){ if(dp[i][j-1][0][c-1]!=-1) dp[i][j][0][c]=max(dp[i][j][0][c],dp[i][j-1][0][c-1]+a[i][j]); } for(int c=0;c<=k;c++){ if(dp[i][j-1][1][c]!=-1) dp[i][j][0][1]=max(dp[i][j][0][1],dp[i][j-1][1][c]+a[i][j]); } for(int c=1;c<=k;c++){ if(dp[i-1][j][1][c-1]!=-1) dp[i][j][1][c]=max(dp[i][j][1][c],dp[i-1][j][1][c-1]+a[i][j]); } for(int c=0;c<=k;c++){ if(dp[i-1][j][0][c]!=-1) dp[i][j][1][1]=max(dp[i][j][1][1],dp[i-1][j][0][c]+a[i][j]); } } } ll ans=-1; for(int i=1;i<=k;i++){ ans=max({ans,dp[n][m][0][i],dp[n][m][1][i]}); } cout<<ans; fclose(stdin); fclose(stdout); return 0; }1周前 来自 广东
0
有帮助，赞一个