Submission #1189180

---

Source Code Expand

#include <iostream>

using namespace std;

int dis(int x, int y){
        if(x - y >= 0)
                return x - y;
        else
                return y - x;
}

int min(int x, int y){
        if(x < y)
                return x;
        else
                return y;
}

int StepNum(int R, int G, int B){
        //探索するのは-(R + G + B) - 100 <= x <= R + G + B + 100// 
        int width = (R + G + B + 100) * 2 + 1;

        //dp[i][j]はx = i - (R + G + B) - 100まででj個マーブルを並べるときの最適の手数//
        int dp[width][R + G + B + 1];

        int i, j;
        //左からdp matrixを埋めていく//
        //実現できないものには負の数を与える//
        dp[0][0] = 0;
        dp[0][1] = dis(-(R + G + B) - 100, -100);
        for(i = 2; i <= R + G + B; i++)
                dp[0][i] = -1;

        for(i = 1; i < width; i++){
                //x座標//
                int x = i - (R + G + B) - 100;
                int distance;
                for(j = 0; j <= R + G + B; j++){
                        //マーブルの初期位置からいまいる点までの距離//
                        if(j <= R)
                                distance = dis(x, -100);
                        else if(j <= R + G)
                                distance = dis(x, 0);
                        else if(j <= R + G + B)
                                distance = dis(x, 100);

                       //1個も置かない場合は0//                
                        if(j == 0)
                                dp[i][j] = 0;
                        //1つ前の位置でj - 1個置けないなら無理//
                        else if(dp[i - 1][j - 1] < 0)
                                dp[i][j] = -1;
                        //置ける場合はxの位置にマーブルを1つ持ってくる//
                        else if(dp[i - 1][j] < 0)
                                dp[i][j] = dp[i - 1][j - 1] + distance;
                        //1つ前の位置でj個置ける場合は小さい方を採用//
                        else
                                dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1] + distance);
                }
        }

        return dp[width - 1][R + G + B];
}

int main(){
        //マーブルの数R, G, B//
        int R, G, B;
        cin >> R >> G >> B;

        //DPで最適な手数を探索//
        int answer = StepNum(R, G, B);

        cout << answer << endl;

        return 0;
}

Submission Info

Judge Result