ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

KUPC 2014 J カード

概要


問題文はこちら
http://kupc2014.contest.atcoder.jp/tasks/kupc2014_j

解法


動的計画法で解くことができる。

dp[日にち][カードの所持数]=持っているお金の最大値

ソースコード

#include <bits/stdc++.h>

#define REP(i, x, n) for(int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back

using namespace std;

int N, M, P;
int x[20];
int sum[20];
int dp[100 + 1][100 + 1]; // dp[日にち][枚数]

int solve() {
  rep(i, M) {
    sum[i] = x[i];
    if(i) sum[i] += sum[i - 1];
  }
  
  memset(dp, -1, sizeof(dp));
  dp[0][0] = 0;
  
  rep(i, N + 1) rep(j, N + 1) if(dp[i][j] != -1) {
    int money = dp[i][j] + P;
    
    dp[i + 1][j] = max(dp[i + 1][j], money);

    rep(k, M) {
      if(j + k + 1 > N) break;
      if(sum[k] > money) break;
      dp[i + 1][j + k + 1] = max(dp[i + 1][j + k + 1], money - sum[k]);
    }
  }

  int ans = 1000000;
  rep(i, N + 1) if(dp[i][N] != -1) ans = min(ans, i);

  return ans;
}

int main() {
  cin >> N >> M >> P;
  
  rep(i, M) cin >> x[i];
  
  cout << solve() << endl;
}