Educational DP ContestのB問題, C問題

#[レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】](https://qiita.com/e869120/items/eb50fdaece12be418faa#2-3-%E5%88%86%E9%87%8E%E5%88%A5%E5%88%9D%E4%B8%AD%E7%B4%9A%E8%80%85%E3%81%8C%E8%A7%A3%E3%81%8F%E3%81%B9%E3%81%8D%E9%81%8E%E5%8E%BB%E5%95%8F%E7%B2%BE%E9%81%B8-100-%E5%95%8F)

###前回の続き
[全探索：全列挙, 工夫して通り数を減らす全列挙, ビット全探索](https://qiita.com/RubyLrving/items/449048d8a8ce9ae14d7c)

###解説
[動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集](https://qiita.com/drken/items/dc53c683d6de8aeacf5a)

##B問題
###[B - Frog 2](https://atcoder.jp/contests/dp/tasks/dp_b)

A問題との違いは、分岐パターンが変数になった事です。
簡単ですね。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cctype>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

ll dp[100002];
int H[100002];

int main(int argc, const char * argv[]) {
    int N, K;
    cin >> N >> K;

    rep(i, N+2) dp[i] = INF;
    rep(i, N) cin >> H[i];
    
    dp[0] = 0;
    
    for(int i=1; i<N; i++){
        for(int j=1; j<=K; j++){
            if(i-j>=0) chmin(dp[i], dp[i-j] + abs(H[i]-H[i-j]));
        }
    }
    cout << dp[N-1] << endl;
    
    return 0;
}
```

###[C - Strange Bank](https://atcoder.jp/contests/abc099/tasks/abc099_c)
###dpデーブルを使わないdp

貪欲法だと、
１４-9=5みたいな結果の際に、６回の引き出しが必要。
１４-6=8、8-6=2で４回の引き出しになり9を使用した時より少ない。
つまり貪欲法が使えない。

その為、６を使用する金額、９を使用する金額を分ける全探索をとります。
0~iまでの金額を６に使用します。
N-iの金額を９に使用します。

そうすると16、１７みたいな金額は、６まで６を使用（１６−６＝１０）。
１０−９＝１で３回の引き出し回数を導き出すことができます。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cctype>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

int main(int argc, const char * argv[]) {
    int N;
    cin >> N;
    
    int res = N;
    for(int i=0; i<=N; i++){
        int cc=0;
        int t=i;
        while(t>0){ cc+=t%6; t/=6; }
        t = N - i;
        while(t>0){ cc+=t%9; t/=9; }
        if(res>cc) res = cc;
    }
    cout << res << endl;
    
    return 0;
}
```

##C問題
###[C - Vacation](https://atcoder.jp/contests/dp/tasks/dp_c)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cctype>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

ll dp[100002][3];
ll A[100002][3];



int main(int argc, const char * argv[]) {
    int N;
    cin >> N;

    rep(i, N) cin >> A[i][0] >> A[i][1] >> A[i][2];
    
    for(int i=0; i<N; i++){
        for(int j=0; j<3; j++){
            for(int k=0; k<3; k++){
                if(j==k) continue;
                chmax(dp[i+1][k], dp[i][j] + A[i][k]);
            }
        }
    }
    
    ll res=0;
    rep(i, 3) res = max(res, dp[N][i]);
    cout << res << endl;
    
    return 0;
}
```