【AtCoder】ABC040 C. 柱柱柱柱柱

AtCoderの問題

C: 柱柱柱柱柱 - AtCoder Beginner Contest 040 | AtCoder

参考書

プログラミングコンテストチャレンジブック [第2版]

難しさ（初心者目線）

・考え方**

・実装***

・面白さ**

問題概要

・柱が1列にN本並んでいる.
・それぞれの柱の高さはである.
・1本目からN本目まで飛び移りながら移動したい.
・飛び移るには飛び移る前と後の柱の高さの差の絶対値の体力を消耗する.
・最大1本飛ばしできる.
・消費する体力を最小にしたい、最小値を求めよ.

方針

動的計画法か深さ優先全探索(メモ化再帰)で解くことができる.好みだと思う.

動的計画法の場合

dp[i]:=i番目の柱に行くために消費する体力の最小値とする.
これは1個前から来た方が良いのか2個前から来た方が良いのかの二択である(1個前と2個前の柱に行くために消費する体力はすでに最小値を求めているので).
つまり dp[i] = min(dp[i-1]+1個前の柱との差の絶対値, dp[i-2]+2個前の柱との差の絶対値)
2本目の柱は1本目の柱からしか来れないことに注意.

深さ優先全探索の場合

メモ化再帰を用いてとく.

動的計画法コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

//動的計画法
//dp[i]:=i番目の柱に行く最小値

int a[100000];
int N;
ll dp[100001];
int main(){
    cin>>N;
    FOR(i, 0, 100000) a[i] = 0;
    FOR(i, 0, N) cin>>a[i];
    FOR(i, 0, 100001) dp[i] = 999999999999;
    dp[0] = 0;
    dp[1] = 0;//1番目の柱に行く最小値はもちろん0
    dp[2] = abs(a[1] - a[0]);//2番目の柱には1番目からくるしかない
    FOR(i, 3, N+1){
        //1個前と2個前どっちからきた方がi番目は最小値になるか
        dp[i] = min(dp[i-2]+abs(a[i-1]-a[i-3]), dp[i-1]+abs(a[i-1]-a[i-2]));
    }
    cout << dp[N] << endl;
}

メモ化再帰コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

int a[100000];
int N;
ll INF = -1;
//再帰関数+メモ化
//位置は0~N-1
ll dp[100000][2];
ll dfs(int n, int bef){
    //N本目についたらおしまい
    if(n == N-1) return abs(a[N-1] - a[n-bef]);
    //N本目を超えてしまう場合注意
    if(n == N) return abs(a[N-1] - a[N-2]);
    //すでに計算済みならそれを返す
    if(dp[n][bef-1]!=INF) return dp[n][bef-1];
    
    ll ret = abs(a[n] - a[n-bef]);
    ret += min(dfs(n+1, 1), dfs(n+2, 2));
    return dp[n][bef-1] = ret;
}

int main(){
    cin>>N;
    FOR(i, 0, 100000) a[i] = 0;
    FOR(i, 0, N) cin>>a[i];
    FOR(i, 0, 100000) FOR(j, 0, 2) dp[i][j] = INF;
    cout << min(dfs(1, 1), dfs(2, 2)) << endl;
}