P1853 投资的最大效益

题目背景

约翰先生获得了一大笔遗产,他暂时还用不上这一笔钱,他决定进行投资以获得更大的效益。银行工作人员向他提供了多种债券,每一种债券都能在固定的投资后,提供稳定的年利息。当然,每一种债券的投资额是不同的,一般来说,投资越大,收益也越大,而且,每一年还可以根据资金总额的增加,更换收益更大的债券。

题目描述

例如:有如下两种不同的债券:①投资额 $4000,年利息$ 400;②投资额 $3000,年利息$ 250。初始时,有 $10000的总资产,可以投资两份债券①债券,一年获得$ 800的利息;而投资一份债券①和两份债券②,一年可获得 $900的利息,两年后,可获得$ 1800的利息;而所有的资产达到 $11800,然后将卖掉一份债券②,换购债券①,年利息可达到$ 1050;第三年后,总资产达到 $12850,可以购买三份债券①,年利息可达到$ 1200,第四年后,总资产可达到$14050。

现给定若干种债券、最初的总资产,帮助约翰先生计算,经过n年的投资,总资产的最大值。

输入输出格式

输入格式:

第一行为三个正整数s,n,d,分别表示最初的总资产、年数和债券的种类。

接下来d行,每行表示一种债券,两个正整数a,b分别表示债券的投资额和年利息。

输出格式:

仅一个整数,表示n年后的最大总资产。

输入输出样例

输入样例#1: 复制
10000 4 2
4000 400
3000 250
输出样例#1: 复制
14050

说明

s≤10^6,n≤40,d≤10,a≤10^4,且a是1000的倍数,b不超过a的10%。

//。。投资并不是把钱减去,相当于把钱借给别人用,但是钱还是你的 
//而且投资的利息是当年投当年就给的

//所以这就是个完全背包问题了
//每种债券都可以选无数次,只要钱够就可以
//dp[s]表示我们花费数量为s的钱可以获得的最大效益
//所以我们到年底的钱就是s+dp[s]
//也就是说我们的资产在不断变更,dp循环的上界也在不断变
//但是从题目的数据范围可以看出来最后的钱肯定不会超过1e7
//所以直接开个1e7的数组搞就可以了 

//当然了题目中说a是1000的倍数,可以将数据压缩1000倍去做
//但是数据水啦 

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N=1e7+5;
const int M=50;

int s,n,d;
int a[M],b[M];
int dp[N];

inline int read()
{
    char c=getchar();int num=0;
    for(;!isdigit(c);c=getchar());
    for(;isdigit(c);c=getchar())
        num=num*10+c-'0';
    return num;
}

int main()
{
    s=read(),n=read(),d=read();
    for(int i=1;i<=d;++i)
        a[i]=read(),b[i]=read();
    for(int A=1;A<=n;++A)
    {
        for(int i=1;i<=d;++i)
        {
            for(int j=a[i];j<=s;++j)
                dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
        }
        s+=dp[s];
    }
    printf("%d",s);
    return 0;
}
原文地址:https://www.cnblogs.com/lovewhy/p/8969753.html