【洛谷P2134】 百日旅行

題目背景

重要的不是去哪里，而是和你在一起。——小紅

對小明和小紅來說，2014年7月29日是一個美好的日子。這一天是他們相識100天的紀念日。

（小明：小紅，感謝你2場大考時默默的支持，100個日夜的陪伴；感謝你照亮我100個美好的日子，給我留下無數美好的回憶……在這個美好的日子里，我準備帶你去旅行。）

題目描述

小明和小紅還剩下N天的假期，小明可以安排旅行的計劃。如果連續X天旅游，小明需要花旅行費用\(P*X*X\)元；如果連續X天不旅游，小明需要請小紅吃飯，花費為Q*X元。（P,Q都是輸入的常數）

請你幫小明寫一個程序，計算出假期里他至少需要花費多少元。

輸入輸出格式

輸入格式：

一行，3個空格隔開的正整數N，P，Q。

輸出格式：

一行，一個正整數表示小明至少需要花費多少元。

經過分析，可以發現對于吃飯，我們只在乎它的時間總量，然后對于旅行,我們已經知道旅行的時間是n-吃飯的時間，又因為計算公式中含有平方，所以我們需要關心這n-i的時間分成了幾段。

這樣就可以開始寫\(n^2\)的算法了。

第一層枚舉吃飯時間，第二層枚舉旅行時間分為多少段，\(O(1)\)計算即可。

code：

#include<iostream> #include<cstdio> using namespace std; inline int read(){int sum=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0';ch=getchar();}return sum*f; } int n,p,q,ans=2147483647; int main(){n=read();p=read();q=read();if(q<=p){printf("%d\n",n*q);return 0;}for(int i=0;i<=n;i++){for(int j=1;j<=min(n-i,i+1);j++){ // int j=i+1;int tmp=i*q+((n-i)/j+1)*((n-i)/j+1)*p*((n-i)%j)+((n-i)/j)*((n-i)/j)*p*(j-(n-i)%j);ans=min(ans,tmp);}}printf("%d\n",ans);return 0; }

寫完就可以發現最優情況下旅行的時間被平均分是最好的，所以找到了凸性函數的極值點直接帶就可以了。

100分

code：

#include<iostream> #include<cstdio> using namespace std; inline int read(){int sum=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0';ch=getchar();}return sum*f; } int n,p,q,ans=2147483647; int main(){n=read();p=read();q=read();if(q<=p){printf("%d\n",n*q);return 0;}for(int i=0;i<=n;i++){int j=i+1;int tmp=i*q+((n-i)/j+1)*((n-i)/j+1)*p*((n-i)%j)+((n-i)/j)*((n-i)/j)*p*(j-(n-i)%j);ans=min(ans,tmp);}printf("%d\n",ans);return 0; }

轉載于:https://www.cnblogs.com/wangxiaodai/p/9776036.html

總結

以上是生活随笔為你收集整理的DP【洛谷P2134】 百日旅行的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。