？没有题解真的假的

前面忘了后面忘了先写程序框架

#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 10;

int m, n, year, a[N], b[N], dp[N];

int main()
{
	cin >> m >> year >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i] >> b[i];

    /*...*/
	
	return 0;
}

疑似完全背包例题

完全背包就是一个物品可以选取无限次的0-1背包，根据题目背景得知我们每年都要重新购买新的债券，故在外面套个 while

好的， while 实现了 可以选取无限次（即上述 while 循环），所以接下来就是质朴の0-1背包力

故：

	while (year--)
	{
		for (int i = 1; i <= n; i++)
			for (int j = a[i]; j <= m; j++)
				dp[j] = max(dp[j], dp[j - a[i]] + b[i]);
	}

    cout << dp[m];

但是毫无疑问是错的……

错在每一年的本金其实是去年的 初始资金+去年债券的年利息

#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 10;

int m, n, year, a[N], b[N], dp[N], money; // money是每一年结束后的总资产

int main()
{
	cin >> m >> year >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i] >> b[i];

    money += m; // 首先把一开始的本金加上
	while (year--) // 一个物品可以拿无限次
	{
		for (int i = 1; i <= n; i++)
                                //   ↓ 直接以去年总资产为初始资金
			for (int j = a[i]; j <= money; j++)
				dp[j] = max(dp[j], dp[j - a[i]] + b[i]);
		money += dp[money]; // 加上今年的年利息
		memset(dp, 0, sizeof(dp)); // 重置dp数组
	}

    cout << money; // 这时money即为year年下来的所有总资产
	
	return 0;
}

这时候提交就会发现……

100 Wrong Answer

最后一个测试点居然

#1 Runtime Error 832ms 115 MiB

爆了

仔细读题我们发现了

$a$ 是 $1000$ 的倍数

🤓👆

于是我们可以把 a[i] /= 1000 以优化空间

因为 a[i] /= 1000 了，

所以就要把 for (int j = a[i]; j <= ans; j++) 改成 for (int j = a[i]; j <= ans / 1000; j++)

因为 for (int j = a[i]; j <= ans / 1000; j++)，

所以根本就到不了 dp[ans],

所以 ans += dp[ans]; 要改成 ans += dp[ans / 1000];

故改为：

    /*...*/

	cin >> m >> year >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i] >> b[i], a[i] /= 1000; // "/= 1000"
	
    /*...*/

	while (year--)
	{
		for (int i = 1; i <= n; i++)
			for (int j = a[i]; j <= money / 1000; j++) // "/ 1000"
				dp[j] = max(dp[j], dp[j - a[i]] + b[i]);
		money += dp[money / 1000]; // "/ 1000"
		memset(dp, 0, sizeof(dp));
	}

    /*...*/

完整代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 10;

int m, n, year, a[N], b[N], dp[N], money; // money是每一年结束后的总资产

int main()
{
	cin >> m >> year >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i] >> b[i], a[i] /= 1000; // "/= 1000"
	
	money += m; // 首先把一开始的本金加上
	while (year--) // 一个物品可以拿无限次
	{
		for (int i = 1; i <= n; i++)
		                     	//   ↓ 直接以去年总资产为初始资金
			for (int j = a[i]; j <= money / 1000; j++) // "/ 1000"
				dp[j] = max(dp[j], dp[j - a[i]] + b[i]);
		money += dp[money / 1000]; // 加上今年的年利息 // "/ 1000"
		memset(dp, 0, sizeof(dp)); // 重置dp数组
	}
	
	cout << money; // 这时money即为year年下来的所有总资产
	
	return 0;
}