KUPC 2014 J - カード

問題

カードをN枚買いたい。
最初0円もっていて、毎日のはじめにP円もらえる。


カードは一日M枚まで買えて、i枚買うのにx[i]円かかる。
カードを合計N枚買うのにかかる日数の最小値を求めよ。

制約条件

N≦100
M≦20
P≦10万
x[1]≦P

方針

最後の条件から100日以内でカードは買える。
dp[i][j]を、i日でj枚のカードを集めるときの、残金の最大値としてDPすればいい。

ソースコード

int n, m, p;
int x[21];

map<ll, ll> dp[101]; //dp[i][j], i枚をj日で買うときの最安値

int main(){
	cin >> n >> m >> p;
	rep(i, m) cin >> x[i + 1], x[i + 1] += x[i];
	
	int ans = inf;
	
	dp[0][0] = 0;
	rep(i, n){
		each(j, dp[i]){
			ll money = j->first * p - j->second;
			for(int k = 1; k <= m && i + k <= n; k++){
				
				ll nd = 0, np = j->second + x[k];
				if(money >= x[k]) nd = j->first + 1;
				else nd = j->first + (x[k] - money + p - 1) / p;
				
				if(!dp[i + k].count(nd)) dp[i + k][nd] = np;
				else dp[i + k][nd] = min(dp[i + k][nd], np);
			}
		}
	}
	cout << dp[n].begin()->first << endl;
	
	return 0;
}