P1853 投资的最大效益

admin

https://www.luogu.org/problemnew/show/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%。

type尧

1. //
   
2. #include<iostream>
   
3. #include<cstdlib>
   
4. #include<cstdio>
   
5. #include<algorithm>
   
6. #define maxium 100000000
   
7. using namespace std;
   
8. int s,n,d;
   
9. struct node{
   
10.         int need,money;
    
11. }bonds[15];
    
12. int m[50];
    
13. int f[maxium];
    
14. void read()
    
15. {
    
16.         cin>>s>>n>>d;
    
17.         for(int i=1;i<=d;i++)
    
18.                 cin>>bonds[i].need>>bonds[i].money;
    
19.         return;
    
20. }
    
21. void work()
    
22. {
    
23.         read();
    
24.         m[0]=s;
    
25.         for(int i=1;i<=n;i++){
    
26.                 for(int j=1;j<=d;j++)
    
27.                         for(int k=bonds[j].need;k<=m[i-1];k++)
    
28.                                 f[k]=max(f[k],f[k-bonds[j].need]+bonds[j].money);
    
29.                 m[i]=f[m[i-1]]+m[i-1];
    
30.         }
    
31.         cout<<m[n];
    
32.         return;
    
33. }
    
34. int main()
    
35. {
    
36.         work();
    
37.         return 0;
    
38. }
    

复制代码