DFS,40pts求助
查看原帖
DFS,40pts求助
285617
黑影洞人楼主2022/7/20 14:19
#include<cstdio>
#include<algorithm>
#include<set>
#define int long long
using namespace std;
int ans=2e11,n,g,b,d,lz,fi;
struct node{
	int x,y;
	bool operator<(const node &fifi)const{return x<fifi.x;}
};
set<node> st;
void dfs(int x,int you,int cost){
	//printf("%lld\n",ans);
	set<node>::iterator it=st.lower_bound({x+1,0});
	if(x==d)return (void)(ans=min(ans,cost));
	if(you<it->x-x)return;
	if(cost>ans)return;
	if(you>=it->x-x&&it->x==d)return (void)(ans=min(ans,cost));
	dfs(it->x,you-(it->x-x),cost);
	for(int i=you-(it->x-x)+1;i<=g;i++)dfs(it->x,i,cost+it->y*(i-(you-(it->x-x))));
}
signed main(){
	scanf("%lld%lld%lld%lld",&n,&g,&b,&d);
	for(int i=1;i<=n;i++){
		int a,bb;
		scanf("%lld%lld",&a,&bb);
		st.insert({a,bb});
		if(a-lz>g)return puts("-1"),0;
		lz=a;if(i==1)if(a>b)return puts("-1"),0;
	}
	if(d-lz>g)return puts("-1"),0;
	//if(b>d)
	st.insert({d,0});
	dfs(0,b,0);
	printf("%lld",ans);
	return 0;
}


2022/7/20 14:19
加载中...