TopCoder SRM 612 Div1 Easy EmoticonsDiv1 [1人競技プログラミング Advent Calendar 2016 12日目]

今日の分はサクッと解けた。

この記事は1人競技プログラミング Advent Calendar 2016 12日目の記事です。

問題概要：
TopCoder Statistics - Problem Statement
コンテストで良い成績を得たので友人に笑顔の絵文字を大量に送り付けます。
最初に絵文字が1つ入力された状態で、下記の3つのどれか1つを時間1で行う事が出来る。
・今書かれている絵文字全てをコピーする
・コピーした絵文字を貼り付ける
・終端から1文字削除する

N個の絵文字を送り付ける際の最小の時間を求めよ。

解いた方法：
Nが小さい(2<= N <= 1000)ので、全部試す。
i文字文コピーした際にペーストして、最小手を更新する際に戻れるだけ戻り、またペーストして…といった感じで配列に最小で移動できる手数を保持しておけばよい。
折り返しが発生する可能性があるので十分に要素数を持っておくといいかも？(例えば1002から折り返したら最短手になる可能性とかありそう。)

#include<bits/stdc++.h>

#define MP make_pair
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n) for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

class EmoticonsDiv1 {
    public:
    int smiles;
    int printSmiles(int _smiles) {
        smiles = _smiles;

        int memo[2002];
        REP(i, 2002){ memo[i] = INF; }

        memo[0] = 0;
        REP(i, smiles){
            int paste = i+1;
            int cost = memo[i] + 1;

            for(int j=i+paste; true; j += paste){
                cost++;
                memo[j] = min(memo[j], cost);
                for(int k=j-1; k>=0; k++){
                    if(memo[k] <= memo[k+1]) break;
                    memo[k] = memo[k+1] + 1;
                }
                if(j >= smiles) break;
            }
        }

        return memo[smiles-1];
    }
};