KUPC2014 : J - カード

あれ、600点問題まではさほど難しくない…？
http://kupc2014.contest.atcoder.jp/tasks/kupc2014_j

問題

N枚のカードを手に入れたい。
プレイヤーは1日P円を入手できる。(過去の余ったお金は使いまわせる)
1日あたりカードを最大M枚購入可能だが、k枚買うにはsum(x[1..k])分のお金がかかる。

N枚カードを得るのに最短何日かかるか。

解法

この問題はP,xは大きいがN,Mは小さい。
そこでdp[経過日数][所持カード枚数] := 条件を満たす残金の最大値 としてDPするだけ。
O(N^2*M)で終わる。

int N,M,P;
int X[101],S[101];
int dp[101][101];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M>>P;
	FOR(i,M) cin>>X[i];
	FOR(i,M) S[i+1]=S[i]+X[i];
	
	MINUS(dp);
	dp[0][N]=0;
	FOR(i,N) FOR(x,N+1) if(dp[i][x]>=0) {
		y=dp[i][x]+P;
		FOR(j,min(x,M)+1) if(S[j]<=y) {
			dp[i+1][x-j]=max(dp[i+1][x-j],y-S[j]);
			if(x-j==0) return _P("%d\n",i+1);
		}
	}
}

まとめ

Mは小さいけどBitDPでもないし、正答者もDより多い。
この問題は一体なんだったんだ…。