読者です 読者をやめる 読者になる 読者になる

ヘクトのメモ

なんとなくいろいろ書いていくと思います.

AOJ 2607 Invest Master

大学のICPC練習会で,Jag Summer 2013 Day3を1週間くらいやっていました.
(くるくるくるりんは除く)
解いた分だけまとめていきます.


問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2607


解法
答えが10^5以下になるという制約が1つ目の重要な点
次に,手数料がかからないので買った次の日に全売却しても問題ない.
そして,株は任意の単位を買える.
個数制限なしナップザックDPで解ける..
dpテーブルは,dp[現在の金額]=次の日に得られる金額
省メモリのために,dpテーブルは使いまわせる.

計算量はO(DNP) (Pは所持金の上限 10^5)

ソースコードは以下の通り

const int pmax=100010;

int dp[pmax];
int p[15][15];

int main(void){
	int n,d,x;
	cin >> n >> d >> x;
	rep(i,d)rep(j,n) cin >> p[i][j];

	rep(i,d-1){
		rep(j,x+1) dp[j]=j;
		rep(j,n)rep(k,x+1) if(k-p[i][j]>=0) dp[k]=max(dp[k],dp[k-p[i][j]]+p[i+1][j]);
		int y=0;
		rep(j,x+1) y=max(y,dp[j]);
		x=y;
	}
	cout << x << endl;
	return 0;
}