华师一附中OI组
标题:
P1853 投资的最大效益
[打印本页]
作者:
admin
时间:
2018-10-2 19:46
标题:
P1853 投资的最大效益
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尧
时间:
2018-11-4 18:58
//
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define maxium 100000000
using namespace std;
int s,n,d;
struct node{
int need,money;
}bonds[15];
int m[50];
int f[maxium];
void read()
{
cin>>s>>n>>d;
for(int i=1;i<=d;i++)
cin>>bonds[i].need>>bonds[i].money;
return;
}
void work()
{
read();
m[0]=s;
for(int i=1;i<=n;i++){
for(int j=1;j<=d;j++)
for(int k=bonds[j].need;k<=m[i-1];k++)
f[k]=max(f[k],f[k-bonds[j].need]+bonds[j].money);
m[i]=f[m[i-1]]+m[i-1];
}
cout<<m[n];
return;
}
int main()
{
work();
return 0;
}
复制代码
欢迎光临 华师一附中OI组 (http://hsyit.cn/)
Powered by Discuz! X3.2