Help us understand the problem. What is going on with this article?

【Atcoder】DPまとめコンテスト M candies

More than 1 year has passed since last update.

こんばんは:runner:
今日はDPまとめコンテストのM candiesを解いてみようと思います!

問題概要

N人の子供たちにK個のあめを配る。ただし子供iに配るあめは0以上ai個でないといけない。

解法

i人目までの子供にj個のあめを配ることを考え、この場合の数をdp[i][j]とする。
この状態にi-1人目の状態から至るためには、以下からの遷移が考えられる。

  • i-1人目までにj個配る。i人目には0個配る。
  • i-1人目までにj-1個配る。i人目には1個配る。
  • i-1人目までにj-2個配る。i人目には2個配る。
  • (中略)
  • i-1人目までにj-ai-1個配る。i人目にはai-1個配る。

数式にすると

$ dp[i][j] = dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j-2]+\cdots+ dp[i-1][j-a_{i-1}] \tag{1} $

式が長い!
このjj-1を代入して書き換えます。

$ dp[i][j-1] = dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j-3]+\cdots+ dp[i-1][j-a_{i-1}-1] \tag{2} $

(1)から(2)を引くとスッキリ。

$$dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-a_{i-1}-1]$$

実装

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
typedef long long ll;
int n,k;
vector<ll> a;
ll dp[110][100010];
ll mod = 1000000007;

int main(){
 cin >> n >> k;
 a.resize(n);
 for(int i = 0; i < n; ++i) cin >> a[i];
 for(int i = 0; i <= n; ++i) dp[i][0] = 1; //i人目までに0個配る方法は1通り

 for(int i = 1; i <= n; ++i){
   for(int j = 1; j <= k; ++j){
     dp[i][j] = (dp[i - 1][j] + dp[i][j - 1])%mod;
     if(j - a[i - 1] - 1 >= 0){
       dp[i][j] = (dp[i][j] + mod - dp[i - 1][j - a[i - 1] - 1])%mod;
     }
   }
 }
 cout << dp[n][k] << endl;
 return 0;
}

DPは奥が深いですね:bride_with_veil_tone2:

kssd0102
Atcoder初心者勉強ブログ rank水色目指して奮闘中〜 理系院卒(航空宇宙)→金融→DS@startup
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away