社区讨论

求助各位巨佬,为何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 条回复,欢迎继续交流。

正在加载回复...