Educational DP ContestのA問題

#[レッドコーダーが教える、競プロ・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)

##動的計画法の勉強を挫折
実は４ヶ月前に勉強をしようと思って挫折しました。
しかしabc184のd問題、またabc183のe問題が動的計画法が関わっているそうです。
ついに後に引けない状況になってきました。

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

###template projectの修正
けんちょんさんの記事を参考に「chmax」、「chmin」を追加。

```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[]) {
    

    return 0;
}
```


##動的計画法：ナップザック DP
###[ALDS_10_A - フィボナッチ数](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_A&lang=ja)

dfsにて実行するとTLEになります。
ここで関数の呼び出しの「fib(n)=fib(n-1)-fib(n-2)」を「fib[i] = fib[i-1] + fib[i-2]」に変更し、Nまでのループ文に変更します。
dpではないですが感覚を掴める問題です。

```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<list>
#include<set>
#include<bitset>

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

ll fib[44];
void FibonacciNumber(){
    int N;
    cin >> N;
    
    fib[0]=1;
    fib[1]=1;
    
    for(int i=2; i<=N; i++){
        fib[i] = fib[i-1] + fib[i-2];
    }
    
    cout << fib[N] << endl;
}
```

###[A - Frog 1](https://atcoder.jp/contests/dp/tasks/dp_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;

int main(int argc, const char * argv[]) {
    int N;
    cin >> N;
    
    vector<int> H(N);
    rep(i, N) cin >> H[i];
    
    ll dp[100002];
    rep(i, N+2) dp[i] = INF;
    
    dp[0]=0;
    
    for(int i=0; i<N; i++){
        chmin(dp[i+1], dp[i] + abs(H[i] - H[i+1]));
        chmin(dp[i+2], dp[i] + abs(H[i] - H[i+2]));
    }
    
    cout << dp[N-1] << endl;
    
    return 0;
}
```

###[C - 柱柱柱柱柱](https://atcoder.jp/contests/abc040/tasks/abc040_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;

int main(int argc, const char * argv[]) {
    int N;
    cin >> N;
    
    vector<int> A(N);
    rep(i, N) cin >> A[i];
    
    ll dp[100002];
    rep(i, N+2) dp[i] = INF;
    
    dp[0]=0;
    
    for(int i=0; i<N; i++){
        chmin(dp[i+1], dp[i] + abs(A[i] - A[i+1]));
        chmin(dp[i+2], dp[i] + abs(A[i] - A[i+2]));
    }
    
    cout << dp[N-1] << endl;
    
    return 0;
}
```

同じコードで解いても勉強にならないのでメモ化再帰を実装します。
過去に計算を行ったノードに関しては処理を行わないようにします。

```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 A[100000];
ll dp[100002];

ll dfs(int N){
    
    if(N==0) return 0;
    if(dp[N]<INF) return dp[N];
    
    chmin(dp[N], dfs(N-1) + abs(A[N] - A[N-1]));
    if(N>1) chmin(dp[N], dfs(N-2) + abs(A[N] - A[N-2]));
    
    return dp[N];
}

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

    rep(i, N) cin >> A[i];
    rep(i, N+2) dp[i] = INF;

    dp[0]=0;

    cout << dfs(N-1) << endl;

    return 0;
}
```

###[C - Typical Stairs](https://atcoder.jp/contests/abc129/tasks/abc129_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;

int dp[100002];

int main(int argc, const char * argv[]) {
    int mod = 1e9+7;
    int N, M;
    cin >> N >> M;

    rep(i, N+2) dp[i] = 0;
    rep(i, M){
        int a;
        cin >> a;
        dp[a] = -1;
        if(a>0 && dp[a-1]==-1) { cout << 0 << endl; return 0; }
    }
    
    dp[0]=0;
    if(dp[1]==0) dp[1] = 1;
    if(dp[1]==-1) dp[2] = 1;
    else dp[2] = 2;
    
    for(int i=3; i<=N; i++){
        if(dp[i]==0){
            if(dp[i-1]==-1) dp[i] = dp[i-2];
            else if(dp[i-2]==-1) dp[i] = dp[i-1];
            else dp[i] = (dp[i-1] + dp[i-2]) % mod;
        }
    }
    cout << dp[N] << endl;
    
    return 0;
}
```

###[Kannondou](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0168)

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

void solve(int N){
    int dp[33];
    rep(i, N+2) dp[i] = 0;
    
    dp[0]=0;
    dp[1]=1;
    dp[2]=2;
    dp[3]=4;
    
    for(int i=4; i<=N; i++){
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
    }
    
    int res = dp[N]/3650;
    if(dp[N]%3650>0) res++;
    
    cout << res << endl;
}

int main(int argc, const char * argv[]) {
    
    vector<int> N;
    while(true){
        int n;
        cin >> n;

        if(n==0) break;
        N.push_back(n);
    }
    
    rep(i, N.size()) solve(N[i]);
    return 0;
}
```