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; }