POJ 2063 Investment

問題

d個の金融商品があり、それぞれの値段および年間の利益が与えられる。
それぞれの商品の金額は固定であるが、同じ種類の商品をいくつも買うことができる。


capの資産を持っている人がn年資産運用するとき、
最大でいくらまで資産を増やせるか求めよ。

制約条件

商品の値段はすべて1000の倍数
商品の年間利回りは10%を超えない
cap≦1000000
d≦10

方針

DPにより、所有資産に対する年間の最大利益をあらかじめ求めておく。
すると、n年間資産を運用したあとの資産はO(n)で求められる。

ソースコード

int n,w[10],v[10],dp[50000];

int main()
{
	int cs; scanf("%d",&cs);
	while(cs--){
		int n,cap,m;
		scanf("%d%d%d",&cap,&m,&n);
		
		rep(i,n)scanf("%d%d",w+i,v+i), w[i]/=1000;
		
		memset(dp,0,sizeof(dp));
		rep(i,50000)rep(j,n)if(i>=w[j])dp[i]=max(dp[i],dp[i-w[j]]+v[j]);
		
		rep(i,m)cap+=dp[cap/1000];
		printf("%d\n",cap);
	}
	
	return 0;
}