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