忍者ブログ
19 August

[PR]

×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

27 March

SRM612 div2 500

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=13041

smiles
個絵文字を入力したいとき、
・今入力されている絵文字を全部クリップボードへコピーする。
・クリップボードからペーストする。
の2種類の操作ができる。
操作する回数の最小値を求めよ。(絵文字は最初に1個入力されている)


感想

DFSが使えて嬉しかったので久々の更新w
(間違っているかもしれません。)


class EmoticonsDiv2 {

	public:
	int printSmiles(int smiles) {
		int ans;
		ans = dfs(1,2,smiles);
		return ans+2;
	}

	int dfs(int clip,int now,int goal){
		int ret = INF;

		if(now == goal)return 0;
		if(now > goal)return INF;
		for(int i=0;i<2;i++){
			if(i==1)ret = min(ret,dfs(clip,now+clip,goal)+1);
			if(i==0)ret = min(ret,dfs(now,now+now,goal)+2);
		}
		return ret;
	}
};

PR