P1853 投资的最大效益

思路

就是一道完全背包板子题，不过是要操作n次然后每次更新背包容量。
但是TLE一个点

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;

int s, n, d;
int dp[10000000];
int v[11], w[11]; 

int main()
{
	scanf("%d %d %d", &s, &n, &d);
	for (int i = 1; i <= d; i++)
	{
		scanf("%d %d", &v[i], &w[i]);
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= d; j++)
		{
			for (int k = v[j]; k <= s; k++)
			{
				dp[k] = max(dp[k], dp[k - v[j]] + w[j]);
			}
		} 
		s = s + dp[s];
		
	}
	printf("%d", s);
	return 0;
	
}

百思不得其解。

审题

对于 \(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\%\)。

这里特意提到了债券价值（即物品体积是1000的整数），所以枚举的时候只要1000、1000地枚举即可。

AC

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;

int s, n, d;
int dp[10000000];
int v[11], w[11]; 

int main()
{
	scanf("%d %d %d", &s, &n, &d);
	int temp = 0x7fffffff;
	for (int i = 1; i <= d; i++)
	{
		scanf("%d %d", &v[i], &w[i]);
		temp = min(temp, v[i]);
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= d; j++)
		{
			for (int k = v[j] / 1000; k <= s / 1000; k++)
			{
				dp[k] = max(dp[k], dp[k - v[j] / 1000] + w[j]);
			}
		}
		s = s + dp[s / 1000];
	}
	printf("%d", s);
	return 0;
	
}