80分求解
  • 板块P1594 护卫队
  • 楼主初嫁QAQ
  • 当前回复1
  • 已保存回复1
  • 发布时间2020/10/29 10:20
  • 上次更新2023/11/5 09:36:57
查看原帖
80分求解
102028
初嫁QAQ楼主2020/10/29 10:20
# include <iostream>
# include <cstdio>
# include <cmath>
# include <cstring>
# define ll long long
using namespace std;
ll W,L,n;
double ans=1324124123;
ll w[1010],sum[1010];
double v[1010],f[1010][15],dp[1010];
int main(){
	scanf("%lld%lld%lld",&W,&L,&n);
	for(ll i=0;i<=n;i++)
		for(ll j=0;j<=11;j++)
			f[i][j]=174817481;
	for(ll i=1;i<=n;i++){
		scanf("%lld%lf",&w[i],&v[i]);v[i]=double(v[i])/double(60);
		//printf("%lf\n",v[i]);
		f[i][0]=v[i],sum[i]=sum[i-1]+w[i];
	}		
	ll p=log(n)/log(2);
	for(ll i=1;i<=p;i++)
		for(ll j=1;j+(1<<i)-1<=n;j++)
			f[j][i]=min(f[j][i-1],f[j+(1<<(i-1))][i-1]);
	for(ll i=0;i<=n;i++)
		dp[i]=41241412;			
	dp[0]=0.0;
	for(ll i=1;i<=n;i++)
		for(ll l=0;l<i;l++){
			if(sum[i]-sum[l]<=W){
				ll e=log(i-l)/log(2);
				double  p=min(f[l+1][e],f[i-(1<<e)+1][e]);
				double r=double(L)/double(p);
				dp[i]=min(dp[l]+r,dp[i]);
					//printf("%lf\n",r);
			}	
		}
	printf("%.1lf",dp[n]);                                                                                                                                                               
	return 0;
}
2020/10/29 10:20
加载中...