mikecat_mixc 2013-11-16 08:50:32

[C] DP書けないんです(´・ω・`) このエントリーをはてなブックマークに追加

投稿者からのアピールポイント

与えられた整数を2の非負整数乗の和で表す方法は何通りあるかを求めよ、という問題(POJ 2229)への自分の回答です。

普通に再帰するとスタックオーバーフローでRuntime Errorになるので、スタックを自前で持って関数呼び出しをシミュレーションしたのですが、

gotoを使うというタブーを犯してしまいました…

#include <stdio.h>

#if 0
#define DEBUG_STACK
#endif

#define MOD_BY 1000000000

int memo[21][1000010];

int tansaku(int max,int now) {
	int stackPointer;
	static int stack[1000010][4];
	int eax=0;

	int result;
	int i;

	stackPointer=0;
	stack[0][0]=max;
	stack[0][1]=now;

tansaku_start:
	max=stack[stackPointer][0];
	now=stack[stackPointer][1];
#ifdef DEBUG_STACK
	printf("called sp=%d (%d,%d)\n",stackPointer,max,now);
#endif

	if(now<0)result=0;
	else if(now==0 || max==0)result=1;
	else if(memo[max][now]>0) {
		result=memo[max][now]-1;
	} else {
		result=0;
		for(i=0;i<=max && (1<<i)<=now;i++) {
			/* result+=tansaku(i,now-(1<<i)); */
			stack[stackPointer][0]=max;
			stack[stackPointer][1]=now;
			stack[stackPointer][2]=result;
			stack[stackPointer][3]=i;
#ifdef DEBUG_STACK
			printf("jump sp=%d (max,now,result,i)=(%d,%d,%d,%d)\n",
				stackPointer,max,now,result,i);
#endif
			stackPointer++;
			stack[stackPointer][0]=i;
			stack[stackPointer][1]=now-(1<<i);
			goto tansaku_start;
		tansaku_returned:
			max=stack[stackPointer][0];
			now=stack[stackPointer][1];
			result=stack[stackPointer][2];
			i=stack[stackPointer][3];
#ifdef DEBUG_STACK
			printf("returned sp=%d eax=%d (max,now,result,i)=(%d,%d,%d,%d)\n",
				stackPointer,eax,max,now,result,i);
#endif

			result+=eax;
			if(result>=MOD_BY)result-=MOD_BY;
		}
		memo[max][now]=result+1;
	}
#ifdef DEBUG_STACK
	printf("return sp=%d eax=%d\n",stackPointer,result);
#endif
	if(stackPointer>0) {
		eax=result;
		stackPointer--;
		goto tansaku_returned;
	}
	return result;
}

int main(void) {
	int N=0;
	scanf("%d",&N);
	printf("%d\n",tansaku(20,N));
	return 0;
}

使い方ヒント: 「これは臭う」という行を見付けたら、各行のsmellをクリックしてマーキングしておきましょう(要Twitter OAuth認証)

コメント(1)

#1 eco_tetsu 2013-11-26 02:31:12  

これって、力業で答え出すものでなくて… 多分ビットをカウントするのでは?

コメント投稿には、twitter認証が必要です。

Twitter認証

このウンコードに臭った人は、こちらのウンコードにも臭ってます

[C++] 関数化しようよ(提案)

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

DXライブラリである座標を中央にして文字...

DrawGraph(50,300,
	buttonImage[loadStat...

鑑賞する »

[C#] 某計算をC#でやろうと深夜テンションで書...

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

翌日デリゲートに直しました

public Tuple<BigInteger, Func<BigInteger...

鑑賞する »