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