dfs做法,75pts
查看原帖
dfs做法,75pts
662413
lmy_2011楼主2023/10/14 18:38

subtask0最后一个点MLE,subtask1WA

#include<bits/stdc++.h>
using namespace std;
double dis1,c,dis2,p,ans;
int n;
double last[505],num[505];
double dfs(int step,double cur)
{
	double tmp=dis2*c;
	if(last[step+1]-last[step]>tmp) 
	{
		return -1;
	}
	double mini=1000000000.0;
	int pos;
	for(int i=step+1;i<=n;i++)
	{
		if(num[i]<mini&&last[step]+tmp>=last[i])
		{
			mini=num[i];
			pos=i;
		}
	}
	if(mini>=num[step])
	{
		double tot=dis1-last[step];
		if(tmp>=tot)
		{
			return num[step]*((tot)/dis2-cur)+ans;
		}
		ans+=num[step]*(c-cur);
		return dfs(step,c-(last[pos]-last[step])/dis2);
	}
	ans+=num[step]*((last[pos]-last[step])/dis2-cur);
	return dfs(pos,0);
}
int main()
{
	cin>>dis1>>c>>dis2>>p>>n;
	last[0]=0;
	last[n+1]=dis1;
	num[0]=p;
	for(int i=1;i<=n;i++)
	{
		cin>>last[i]>>num[i];
	}
	double ans=dfs(0,0);
	if(ans==-1)
	{
		cout<<"No Solution";
		return 0;
	}
	cout<<fixed<<setprecision(2)<<ans;
	return 0;
} 
2023/10/14 18:38
加载中...