社区讨论
求助各位巨佬,为何WA 5个点
P1442铁球落地参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mi6uxrzp
- 此快照首次捕获于
- 2025/11/20 11:14 4 个月前
- 此快照最后确认于
- 2025/11/20 11:14 4 个月前
思路:记忆化搜索
代码如下:
CPP#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct line{
int L,R,H;
}f[1000000];
int n,max_fall;
bool cmp(line f1,line f2){
if(f1.H<f2.H)return true;
else return false;
}
int dp[1000000][2];
//dp[i][0]:从编号为i的板的左端落下到地面的最短距离
//dp[i][1]:从编号为i的板的右端落下到地面的最短距离
int dfs(int p){
bool b1=1,b2=1;
if(f[p].H==0){
dp[p][0]=0;
dp[p][1]=0;
}
else{
int i,j,k,l;
i=p-1;
while(i>0&&f[i].H>=f[p].H)i--;
while((b1==1||b2==1)&&i>0&&f[p].H-f[i].H<=max_fall){
if(b1==1&&f[i].L<f[p].L&&f[p].L<f[i].R){//左端落下
b1=0;
if(dp[i][0]>0)
dp[p][0]=dp[i][0]+(f[p].L-f[i].L)+(f[p].H-f[i].H);
else if(dp[i][0]==0)dp[p][0]=f[p].H-f[i].H;
else{
dfs(i);
if(dp[i][0]>0)
dp[p][0]=dp[i][0]+(f[p].L-f[i].L)+(f[p].H-f[i].H);
else if(dp[i][0]==0)dp[p][0]=f[p].H-f[i].H;
}
if(dp[i][1]>0){
if(dp[p][0]>=0)dp[p][0]=min(dp[p][0],dp[i][1]+(f[i].R-f[p].L)+(f[p].H-f[i].H));
else dp[p][0]=dp[i][1]+(f[i].R-f[p].L)+(f[p].H-f[i].H);
}
else if(dp[i][1]==0){
if(dp[p][0]>=0)dp[p][0]=min(dp[p][0],f[p].H-f[i].H);
else dp[p][0]=f[p].H-f[i].H;
}
else{
dfs(i);
if(dp[i][1]>0)
dp[p][0]=min(dp[p][0],dp[i][1]+(f[i].R-f[p].L)+(f[p].H-f[i].H));
else if(dp[i][1]==0)dp[p][0]=min(dp[p][0],f[p].H-f[i].H);
}
}
if(b2==1&&f[p].L!=f[p].R&&f[i].L<f[p].R&&f[p].R<f[i].R){//右端落下
b2=0;
if(dp[i][0]>0)
dp[p][1]=dp[i][0]+(f[p].R-f[i].L)+(f[p].H-f[i].H);
else if(dp[i][0]==0)dp[p][1]=f[p].H-f[i].H;
else{
dfs(i);
if(dp[i][0]>0)
dp[p][1]=dp[i][0]+(f[p].R-f[i].L)+(f[p].H-f[i].H);
else if(dp[i][0]==0)dp[p][1]=f[p].H-f[i].H;
}
if(dp[i][1]>0){
if(dp[p][1]>=0)dp[p][1]=min(dp[p][1],dp[i][1]+(f[i].R-f[p].R)+(f[p].H-f[i].H));
else dp[p][1]=dp[i][1]+(f[i].R-f[p].R)+(f[p].H-f[i].H);
}
else if(dp[i][1]==0){
if(dp[p][1]>=0)dp[p][1]=min(dp[p][1],f[p].H-f[i].H);
else dp[p][1]=f[p].H-f[i].H;
}
else{
dfs(i);
if(dp[i][1]>0)
dp[p][1]=min(dp[p][1],dp[i][1]+(f[i].R-f[p].R)+(f[p].H-f[i].H));
else if(dp[i][1]==0)dp[p][1]=min(dp[p][1],f[p].H-f[i].H);
}
}
i--;
}
}
return 0;
}
int main(){
scanf("%d%d",&n,&max_fall);
int i,j,k,l,r;
scanf("%d%d",&l,&k);
f[n+2].L=l;f[n+2].R=l;f[n+2].H=k;//小球初始位置看成一块长度为0的板
l=99999999;r=-1;
for(i=1;i<=n;i++){
scanf("%d%d%d",&f[i].H,&f[i].L,&f[i].R);
l=min(l,f[i].L)-1;
r=max(l,f[i].R)+1;
}
f[n+1].L=l;f[n+1].R=r;f[n+1].H=0;//地板
sort(f+1,f+1+n+1,cmp);
for(int i=1;i<=n+2;i++){
dp[i][0]=-1;
dp[i][1]=-1;
}
dfs(n+2);
cout<<dp[n+2][0]<<endl;
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...