P1016 旅行家的预算

题面:https://www.luogu.org/problem/P1016

本题直接贪心之后dfs即可,注意dfs要讨论两种情况. Code: #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> #include<ctime> using namespace std; const int N=10005; int n,f; double ans=100000000.00,d1,c,d2,d[N],p[N],dis[N]; void dfs(int now,double oil,double cost){if(now==n+1){if(cost<ans){ans=cost;}f=1;return;}if(c*d2<dis[now]){return;}double nd=0.00;for(int i=now;i<=n;i++){nd+=dis[i];if(d2*c<nd){break;}dfs(i+1,c-nd/d2,cost+p[now]*(c-oil));dfs(i+1,0.00,cost+max(0.00,p[now]*nd/d2-p[now]*oil));}return; } int main(){scanf("%lf%lf%lf%lf%d",&d1,&c,&d2,&p[0],&n);for(int i=1;i<=n;i++){scanf("%lf%lf",&d[i],&p[i]);dis[i-1]=d[i]-d[i-1];}dis[n]=d1-d[n];dfs(0,0.00,0.00);if(f){printf("%.2lf\n",ans);}else{printf("No Solution\n");}return 0; }

转载于:https://www.cnblogs.com/ukcxrtjr/p/11485355.html

总结

以上是生活随笔为你收集整理的P1016 旅行家的预算的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。