题解 P2134 【百日旅行】

· · 题解

看到楼上都是dp，我来发一个贪心的题解。

由于请小红吃饭的代价是 Q \times x 。

所以如果请小红吃饭的总时间一定那么请小红吃饭的代价就是一定的。

我们考虑当请小红吃饭的天数是 i ，那么需要旅游的总时间就是 n-i ，旅游最多可以被吃饭分成 i+1 次。

我们很容易可以证明每次旅游时间最平均的时候是最优的。

于是我们枚举请小红吃饭的总时间，然后计算旅游的最少代价。

这样时间复杂度为O(n)、空间复杂度为O(1)。

表示大常数选手贪心跑得比dp还要慢一些。

code:

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
const int maxn=2e5+10;
const ll INF=1e17;
ll n,p,q,ans=INF;

ll trav(ll day,ll times) {
    ll x=day/times,y=day%times;
    return p*(times-y)*x*x+p*y*(x+1)*(x+1);//贪心，将除不尽多出的部分也平均分配
}

int main() {
    scanf("%lld%lld%lld",&n,&p,&q);
    for(int i=0;i<=n;++i) ans=min(ans,i*q+trav(n-i,i+1));//枚举请小红吃饭的总时间，计算最小的旅游代价
    printf("%lld",ans);
    return 0;
}