P2134 百日旅行

题目背景

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

对小明和小红来说，2014年7月29日是一个美好的日子。这一天是他们相识100天的纪念日。

（小明：小红，感谢你2场大考时默默的支持，100个日夜的陪伴；感谢你照亮我100个美好的日子，给我留下无数美好的回忆……在这个美好的日子里，我准备带你去旅行。）

题目描述

小明和小红还剩下N天的假期，小明可以安排旅行的计划。如果连续X天旅游，小明需要花旅行费用P*X*X元；如果连续X天不旅游，小明需要请小红吃饭，花费为Q*X元。（P,Q都是输入的常数）

请你帮小明写一个程序，计算出假期里他至少需要花费多少元。

输入输出格式

输入格式：

一行，3个空格隔开的正整数N，P，Q。

输出格式：

一行，一个正整数表示小明至少需要花费多少元。

输入输出样例

输入样例#1：

6 1 7

输出样例#1：

说明

对于20%数据，N<=20。

对于90%数据，N<=1000,P<=2000,Q<=10000.

对于剩下的10%数据，N<=200000,Q<=P<=10000。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,p,q;

long long ans=;

void dfs(int now,int s1,int s2,long long sum){

    if(sum>=ans)return;

    if(now==n+){

        if(s1)sum+=1LL*s1*s1*p;

        if(s2)sum+=1LL*s2*q;

        ans=min(ans,sum);

        return;

    }

    if(s2){

        dfs(now+,,,sum+1LL*s2*q);

        dfs(now+,,s2+,sum);

        return;

    }

    else if(s1){

        dfs(now+,,,sum+1LL*s1*s1*p);

        dfs(now+,s1+,,sum);

        return;

    }

    else {

        dfs(now+,,,sum);

        dfs(now+,,,sum);

    }

}

int main(){

    //freopen("Cola.txt","r",stdin);

    scanf("%d%d%d",&n,&p,&q);

    dfs(,,,);

    cout<<ans;

}

20分暴力深搜

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

int f[],ff[];

int n,m,p,q;

int main(){

    scanf("%d%d%d",&n,&p,&q);

    for(int i=;i<=n;i++){

        f[i]=ff[i]=1e9;

        for(int j=;j<i;j++){

            f[i]=min(f[i],ff[j]+(i-j)*(i-j)*p);

            ff[i]=min(ff[i],f[j]+(i-j)*q);

        }

    }

    printf("%d",min(f[n],ff[n]));

}

90分 O(n^2)的暴力dp

#include<cstdio>

#include<cstring>

#include<iostream>

#include<cmath>

using namespace std;

const int N=;

int f[N],ff[N],g;

int n,m,p,q;

int main()

{

    scanf("%d%d%d",&n,&p,&q);

    if(q<=p){printf("%d",q*n);return ;}

    for(int i=;i<=n;i++){

        for(int j=g+;j<i;j++)

            if(f[g]+(i-g)*(i-g)*p>f[j]+(i-j)*(i-j)*p)g=j;

        f[i]=min(f[i-],ff[i-])+q;

        ff[i]=f[g]+(i-g)*(i-g)*p;

    }

    printf("%d",min(f[n],ff[n]));

}

100分优化dp O(nlogn)左右

巴特西

洛谷P2134 百日旅行

P2134 百日旅行

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章