投资的最大效益

题目背景

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

题目描述

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

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

10000 4 2
4000 400
3000 250

样例输出 #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\%\)。

解题思路

\(f(i,j)\)表示第i年总金额不超过j的所有债券选择方式。

\(dp[j]\)表示当前年份在投资金额为j的情况下所有债券选择方式的盈利情况。

投资金额不得超过当前年份的总资产额。每一年都把股票卖了全部重新买一遍，下一年收取最优投资利润。

题目中给出a为1000的倍数，意味着我们在进行计算的时候可以将原本非常大的数据/1000，缩小了dp数组的存储范围

#include<bits/stdc++.h>
using namespace std;
const int N = 2000000;
int v[N];
int w[N];
int dp[N];
int s,n,d;
int main(){
	cin>>s>>n>>d;
	int ans=0;
	for(int i=1;i<=d;i++){
		int a,b;
		cin>>a>>b;
		v[i]=a;
		w[i]=b;
	}
	for(int i=1;i<=n;i++){
		int all=s/1000;
		for(int t=1;t<=d;t++){
			for(int j=v[t]/1000;j<=all;j++){			
			dp[j]=max(dp[j],dp[j-v[t]/1000]+w[t]);	
			}
		}
		s+=dp[all];
		memset(dp,0,sizeof(dp)); 
	}	
	cout<<s<<endl;	
	return 0;
}