SRM 612 DIV1 Easy - EmoticonsDiv1 (××○)

問題


http://community.topcoder.com/stat?c=problem_statement&pm=10543&rd=15845

・笑顔の顔文字をsmiles分送りたい。
・最初はsmiles1個分送っている。
・1回の操作で、現在の送っている数をクリップボードにコピーできる。
・1回の操作で、クリップボードにコピーしている分の顔文字を送ることができる。
・1回の操作で、現在送っている数を一つ減らすことができる。
・このときの最小の操作回数を求める。

解き方


・dpで解けそう
・パラメータとしては、これまでに送っている顔文字の数、クリップボードにコピーされている顔文字の数で計算量も足りそう
・サンプルは通った

→System Failed

・削除はdpの順序が変わるんで単純なdpでは解けない
・なのでBFSで解く必要がある。距離が小さくなればキューに入れて、smiles数分送ったときの距離が答えになる。

・反省:dpっぽいが、探索の順が一方向でないときは単純に適用できなく、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;
}

};
このエントリーをはてなブックマークに追加