問題
http://community.topcoder.com/stat?c=problem_statement&pm=10543&rd=15845
・笑顔の顔文字をsmiles分送りたい。
・最初はsmiles１個分送っている。
・１回の操作で、現在の送っている数をクリップボードにコピーできる。
・１回の操作で、クリップボードにコピーしている分の顔文字を送ることができる。
・１回の操作で、現在送っている数を一つ減らすことができる。
・このときの最小の操作回数を求める。
解き方
・dpで解けそう
・パラメータとしては、これまでに送っている顔文字の数、クリップボードにコピーされている顔文字の数で計算量も足りそう
・サンプルは通った
→System Failed
・削除はｄｐの順序が変わるんで単純なｄｐでは解けない
・なのでBFSで解く必要がある。距離が小さくなればキューに入れて、smiles数分送ったときの距離が答えになる。
・反省：ｄｐっぽいが、探索の順が一方向でないときは単純に適用できなく、BFSを用いるケースがある。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int d[3001][2001];
class EmoticonsDiv1 {
public: int printSmiles(int smiles) {
FORE(i,0,3001)FORE(j,0,2001)d[i][j]=1e+9;
d[1][0]=0;
queue<pair<int,int> > q;
q.push(make_pair(1,0));
while(!q.empty()){
int a=q.front().first;
int b=q.front().second;
q.pop();
if(a==smiles)return d[a][b];
if(a+b<=3000 && d[a+b][b]>d[a][b]+1){
d[a+b][b]=d[a][b]+1;
q.push(make_pair(a+b,b));
}
if(a<=2000 && d[a][a]>d[a][b]+1){
d[a][a]=d[a][b]+1;
q.push(make_pair(a,a));
}
if(a-1>=0 && d[a-1][b]>d[a][b]+1){
d[a-1][b]=d[a][b]+1;
q.push(make_pair(a-1,b));
}
}
return -1;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int d[3001][2001];
class EmoticonsDiv1 {
public: int printSmiles(int smiles) {
FORE(i,0,3001)FORE(j,0,2001)d[i][j]=1e+9;
d[1][0]=0;
queue<pair<int,int> > q;
q.push(make_pair(1,0));
while(!q.empty()){
int a=q.front().first;
int b=q.front().second;
q.pop();
if(a==smiles)return d[a][b];
if(a+b<=3000 && d[a+b][b]>d[a][b]+1){
d[a+b][b]=d[a][b]+1;
q.push(make_pair(a+b,b));
}
if(a<=2000 && d[a][a]>d[a][b]+1){
d[a][a]=d[a][b]+1;
q.push(make_pair(a,a));
}
if(a-1>=0 && d[a-1][b]>d[a][b]+1){
d[a-1][b]=d[a][b]+1;
q.push(make_pair(a-1,b));
}
}
return -1;
}
};