poj 2063 Investment ( zoj 2224 Investment ) 完全背包

传送门：

POJ:http://poj.org/problem?id=2063

ZOJ：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2224

大意：给你一堆本金，还有投资方案获得的利润。让你进行合理投资，要求若干年后获利最大。

完全背包问题。背包容量就是money,要尽量装满（不是风险投资哇，投资出去必获利）

开始天真的开了400多w（100万*1.1^40）的数组，直接TLE掉。

看了discuss里，因为给的利润为1000的整数倍，故可以将其/1000，那么背包大小也小了，时间上63ms zoj上40ms

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN=45260+10;

int dp[MAXN];

int cost[12],repay[12];

int main()

{

	int T;

	scanf("%d",&T);

	while(T--)

	{

		int money,year,len;

		scanf("%d%d%d",&money,&year,&len);

		for(int i=1;i<=len;i++)

		{

				scanf("%d%d",&cost[i],&repay[i]);

				cost[i]/=1000;

		}

		for(int y=1;y<=year;y++)

		{

			int temp=money/1000;

			for(int i=1;i<=len;i++)

			{

				for(int j=cost[i];j <= temp ;j++)

				{

					dp[j]=max(dp[j], dp[j - cost[i]]+repay[i]);

				}

			}

			money=money+dp[temp];

		}

		printf("%d\n",money);

		memset(dp,0,sizeof(dp));

	}

}

巴特西

poj 2063 Investment ( zoj 2224 Investment ) 完全背包

最新文章

热门文章