学步园

TAG 动态规划

1.设dp[k][n]为长度为k，最大的数不超过n的序列数，也就是题目所求。

dp[k][n]=dp[k][n-1]+dp[k-1][n/2];

0 sec    416 KB

当n = 9, m = 2000, # lists = 19217904335640，所以得用long long，输出时用%lld

2.如果你设dp[k][n]为长度为k，最大数刚好为n的序列数，那你最后还得累加才能得到答案，计算的过程也比较麻烦。

0.05s    416KB

3.如果直接用递归去找，递归次数与最终的结果数成正比。这里会超时。

第一种解法的代码

/* source code of submission 434693, Zhongshan University Online Judge System */<br /> #include <stdio.h><br /> #include <memory.h><br /> const int p2[]={1,2,4,8,16,32,64,128,256,512};<br /> int t,casenum,n,m;<br /> long long dp[10][2001];<br /> void pre()<br /> {<br /> int sum;<br /> for (int i=1; i<=2000; ++i)<br /> {<br /> dp[0][i]=i;<br /> }<br /> for (int k=1; k<10; ++k)<br /> {<br /> for (int j=p2[k]; j<=2000; ++j)<br /> {<br /> dp[k][j]=dp[k][j-1]+dp[k-1][j/2];<br /> }<br /> }<br /> }<br /> int main(int argc, char *argv[])<br /> {<br /> memset(dp, 0, sizeof(dp) );<br /> pre();<br /> scanf("%d", &t);<br /> casenum=0;<br /> while (t-- )<br /> {<br /> ++casenum;<br /> scanf("%d%d", &n, &m);<br /> printf("Case %d: n = %d, m = %d, # lists = %lld/n",casenum,n,m,dp[n-1][m] );<br /> }<br /> return 0;<br /> }<br />

第二种解法的代码：

/* source code of submission 434677, Zhongshan University Online Judge System */<br /> #include <stdio.h><br /> #include <memory.h><br /> int t,casenum,n,m;<br /> long long ans;<br /> long long dp[10][2000];<br /> void pre()<br /> {<br /> int sum;<br /> for (int i=0; i<2000; ++i)<br /> {<br /> dp[0][i]=1;<br /> }<br /> for (int k=1; k<10; ++k)<br /> {<br /> for (int j=1; j<=2000; ++j)<br /> {<br /> if ( dp[k-1][j-1]!=0 )<br /> {<br /> for (int v=j*2; v<=2000; ++v)<br /> {<br /> dp[k][v-1]+=dp[k-1][j-1];<br /> }<br /> }<br /> }<br /> }<br /> }<br /> int main(int argc, char *argv[])<br /> {<br /> memset(dp, 0, sizeof(dp) );<br /> pre();<br /> scanf("%d", &t);<br /> casenum=0;<br /> while (t-- )<br /> {<br /> ++casenum;<br /> scanf("%d%d", &n, &m);<br /> ans=0;<br /> for (int i=0; i<m; ++i)<br /> {<br /> ans+=dp[n-1][i];<br /> }<br /> printf("Case %d: n = %d, m = %d, # lists = %lld/n",casenum,n,m,ans );<br /> }<br /> return 0;<br /> }<br />