投资的最大效益

题目背景

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

题目描述

例如：有如下两种不同的债券：

  1. 投资额 $$4000$，年利息 $$400$；
  2. 投资额 $$3000$，年利息 $$250$。

初始时，有 $$10000$ 的总资产，可以投资两份债券 1 债券，一年获得 $$800$ 的利息；而投资一份债券 1 和两份债券 2，一年可获得 $$900$ 的利息，两年后，可获得 $$1800$ 的利息；而所有的资产达到 $$11800$，然后将卖掉一份债券 2，换购债券 1，年利息可达到 $$1050$；第三年后，总资产达到 $$12850$，可以购买三份债券 1，年利息可达到 $$1200$，第四年后，总资产可达到 $$14050$。

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

1
2
3
10000 4 2
4000 400
3000 250

样例输出 #1

1
14050

提示

对于 $100 \%$ 的数据，$1 \le s \le {10}^6$，$2 \le n \le 40$，$1 \le d \le 10$，$1 \le a \le {10}^4$，且 $a$ 是 $1000$ 的倍数，$b$ 不超过 $a$ 的 $10\%$。

题解

题目解析

剥离其外壳, 实际上还是一个背包问题. 可以无限选, 这就是完全背包. 但是这个有个问题, 这个债券是按年买的, 你的本金每年都会涨. 这到底该怎么办呢？

实际上很简单就能解决, 我们每次跑完一年的之后最大值后把dp数组重置一遍, 并把本金和利率相加作为新的背包容量就好了.

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define CIN_ ios::sync_with_stdio(0)
#define CIN cin.tie(0)
#define MAXN(size) const long long MAXN = size + 100
#define MOD(size) const long long MOD = size
#define mem(name,value) memset(name,value,sizeof(name))
#define fa(i,a,n) for(int i=a;i<=n;++i)
#define fb(i,a,n) for(int i=a;i>=n;--i)
#define T_ int T;cin >> T;while(T--)
typedef pair<int,int> PII;
typedef long long ll;
typedef long double lb;
typedef unsigned long long ull;

MAXN(5e4);
int dp[MAXN],a[MAXN],b[MAXN];

signed main(){
	CIN_;CIN;
	int x,y,z;
	cin >> x >> y >> z;
	fa(i,1,z) cin >> a[i] >> b[i];
	fa(i,1,y){
		mem(dp,0);
		fa(j,1,z){
			fa(k,a[j]/1000,x/1000){
				dp[k] = max(dp[k],dp[k-a[j]/1000]+b[j]);
			}
		}
		x += dp[x/1000];
	}
	cout << x << endl;
	return 0;
}