SRM612 Div1 Easy EmoticonsDiv1

問題概要

Copy,Paste,Deleteがそれぞれ1秒でできるとき,1文字をx文字にするのに最短で何秒かかるか

解法

似たような問題をどこかで見たのでdp[i][j]=(i文字あって,クリップボードにj文字ある状態)はすぐに見えたが,Deleteでdp[i-1][j]に遷移するので普通にループできない.
ということでDijkstraをするがTLE.コストはすべて1なのでBFSにするとAC.
ところで,目的より大きめの数からDeleteするのが最短経路な可能性があり,ある程度DPテーブルを大きめに持たなければいけないはずだが,どれくらい持てばいいのだろうか.とりあえず倍取るようにしてみたが,1000の答えが21なのでそんなに多くある必要はなさそう.だれかわかったら教えてください.

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(int i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<ll,ll>;
using PP=pair<ll,P>;
using vp=vector<P>;
using vpp=vector<PP>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
class EmoticonsDiv1{
public:
    int printSmiles(int n){
        int size=(n+1)*2;
        vvi dp(size,vi(size,INF));
        queue<PP> que;
        dp[1][0]=0;
        que.push(PP(0,P(1,0)));
        while(que.size()){
            PP p=que.front();que.pop();
            int x=p.se.fi,y=p.se.se;
            if(dp[x][y]<p.fi){
                continue;
            }
            if(x+y<size&&dp[x+y][y]>dp[x][y]+1){
                dp[x+y][y]=dp[x][y]+1;
                que.push(PP(dp[x+y][y],P(x+y,y)));
            }
            if(x&&dp[x-1][y]>dp[x][y]+1){
                dp[x-1][y]=dp[x][y]+1;
                que.push(PP(dp[x-1][y],P(x-1,y)));
            }
            if(dp[x][x]>dp[x][y]+1){
                dp[x][x]=dp[x][y]+1;
                que.push(PP(dp[x][x],P(x,x)));
            }
        }
        return *min_element(all(dp[n]));
    }