样例输出28.42求调
查看原帖
样例输出28.42求调
422996
HeCao2008楼主2023/2/12 23:50
#include<bits/stdc++.h>
using namespace std;
const int maxn=114;
int dp[maxn];
double dist[maxn],s[maxn],to,mx,mile,stt;
int n;
int ans=2147483647;
int main(){
	memset(dp,0x3f,sizeof(dp));
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>to>>mx>>mile>>stt>>n;
	for(int i=1;i<=n;i++)cin>>dist[i]>>s[i];
	dp[0]=stt*100;dist[n+1]=to;
	for(int i=1;i<=n;i++){
		for(int j=i-1;j>=0;j--){
		    double now=dist[i]-dist[j];
			if(now>mile*mx)break;
			if(now<=mile*mx/2||dist[i+1]-dist[j]<mile*mx||dp[j]>=dp[n+1])continue;
			 dp[i]=min(dp[i],dp[j]+(int)(round)((double)(now/mile*s[i]))); 
		}
		dp[i]+=200;
	}
	for(int i=n;i>=0;i--){
		if(dist[n+1]-dist[i]>mx*mile)break;
		ans=min(ans,dp[i]);
	}cout<<fixed<<setprecision(2)<<(double)(double(ans)/100);
	return 0;
}
2023/2/12 23:50
加载中...