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;
}
これって、力業で答え出すものでなくて… 多分ビットをカウントするのでは？