2013年10月12日 星期六

STEP5 0093 數御坂妹妹

[DP]
還是不太熟%I64u

主要是遞推公式(狀態懶得畫了:P):








 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define ULLI unsigned long long int
ULLI dp[51];
int main()
{
 int n,m;
 //printf("%d",1<<3);
 scanf("%d %d",&n,&m);;
 memset(dp,0,sizeof(dp));
 dp[0]=1;
 for(int lx=1;lx<=n;lx++)
  dp[lx]=dp[lx-1]<<1;
 for(int lx=n+1;lx<=m;lx++)
  for(int ly=lx-1;ly>=lx-n-1;ly--)
   dp[lx]+=dp[ly];
 printf("%I64u\n",dp[m]);
 return 0;
}

沒有留言:

張貼留言