2023-03-11 21:04 Thammasat University C++ 发布于湖北
关注
美团后端3月11日第二题，求有什么坑
wo是完全不懂为啥只过了45%
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
dp[i][j]=-1;//初始化为-1
if(i==1&&j==1){
dp[i][j]=a[i][j];
continue;
}
if(i-1>=1&&dp[i-1][j]>=0){//可以转移
if(s[i-1][j]==s[i][j]){//相同
dp[i][j]=max(dp[i-1][j]+a[i][j],dp[i][j]);
}
if(s[i-1][j]!=s[i][j]&&dp[i-1][j]-k>=0){//不相同
dp[i][j]=max(dp[i-1][j]+a[i][j]-k,dp[i][j]);
}
}
if(j-1>=1&&dp[i][j-1]>=0){//可以转移的必要条件
if(s[i][j-1]==s[i][j]){//相同
dp[i][j]=max(dp[i][j],dp[i][j-1]+a[i][j]);
}
if(s[i][j-1]!=s[i][j]&&dp[i][j-1]-k>=0){//不相同
dp[i][j]=max(dp[i][j],dp[i][j-1]+a[i][j]-k);
}
}
ans=max(ans,dp[i][j]);//更新结果
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
dp[i][j]=-1;//初始化为-1
if(i==1&&j==1){
dp[i][j]=a[i][j];
continue;
}
if(i-1>=1&&dp[i-1][j]>=0){//可以转移
if(s[i-1][j]==s[i][j]){//相同
dp[i][j]=max(dp[i-1][j]+a[i][j],dp[i][j]);
}
if(s[i-1][j]!=s[i][j]&&dp[i-1][j]-k>=0){//不相同
dp[i][j]=max(dp[i-1][j]+a[i][j]-k,dp[i][j]);
}
}
if(j-1>=1&&dp[i][j-1]>=0){//可以转移的必要条件
if(s[i][j-1]==s[i][j]){//相同
dp[i][j]=max(dp[i][j],dp[i][j-1]+a[i][j]);
}
if(s[i][j-1]!=s[i][j]&&dp[i][j-1]-k>=0){//不相同
dp[i][j]=max(dp[i][j],dp[i][j-1]+a[i][j]-k);
}
}
ans=max(ans,dp[i][j]);//更新结果
}
}
全部评论
我爱果汁
门头沟学院 后端工程师
奇怪，我跟你差不多，我通过全部案例了，我看了半天也不知道我的跟你的哪里差很多
awesome_rookie
蔚来_软件开发
他从左上角的0开始一直有异色＞=0的判断dp元素咋会是负值捏
这是一个昵称111
武汉科技大学 后端工程师
你要判断用来转移的前一个 dp[i][j-1] 是否为 -1，是 -1 就不能转移
不然的话，如果 (i, j-1) 和当前格子颜色相同，而 dp[i][j-1] + a[i][j] > 0，那么这样会更新你的 dp[i][j]，而实际 dp[i][j-1] = -1 代表 (i,j-1) 是不能走到的，也就不能从 (i ,j-1) 走到 (i, j)
SovietPower✨
华东师范大学 C++
f[i][j] 要初始化为 -INF，-1可不够，会走到实际走不到的地方
Hm-
华南农业大学 Java
一样45
诺贝尔
中国科学院大学 算法工程师
说是把dp[1][1]强制为0就过了
ziiikang
字节跳动_后端开发
你是不是没判断走不了的情况，如果dp[i-i][j]和dp[i][j-1]都小于k且与dp[i][j]异色的话，就强制结束了
ringoringo
门头沟学院 Java
一样，也是45
我的名字是假的
美团_后端开发
差不多一样的思路 我也只能45
3266
上海交通大学 算法工程师
咱两写的一样
相关推荐
