sicily 1011. Lenny's Lucky Lotto

发布时间:2017-2-27 19:15:29 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"sicily 1011. Lenny's Lucky Lotto",主要涉及到sicily 1011. Lenny's Lucky Lotto方面的内容,对于sicily 1011. Lenny's Lucky Lotto感兴趣的同学可以参考一下。

1011. Lenny's Lucky Lotto Constraints Time Limit: 1 secs, Memory Limit: 32 MB Description Lenny likes to play the game of lotto. In the lotto game, he picks a list of N unique numbers in the range from 1 to M. If his list matches the list of numbers that are drawn, he wins the big prize.   Lenny has a scheme that he thinks is likely to be lucky. He likes to choose his list so that each number in it is at least twice as large as the one before it. So, for example, if N = 4 and M = 10, then the possible lucky lists Lenny could like are:   1 2 4 8 1 2 4 9 1 2 4 10 1 2 5 10  Thus Lenny has four lists from which to choose. Your job, given N and M, is to determine from how many lucky lists Lenny can choose. Input There will be multiple cases to consider from input. The first input will be a number C (0 < C <= 50) indicating how many cases with which you will deal. Following this number will be pairs of integers giving values for N and M, in that order. You are guaranteed that 1 <= N <= 10, 1 <= M <= 2000, and N <= M. Each N M pair will occur on a line of its own. N and M will be separated by a single space. Output For each case display a line containing the case number (starting with 1 and increasing sequentially), the input values for N and M, and the number of lucky lists meeting Lenny’s requirements. The desired format is illustrated in the sample shown below. Sample Input 3 4 10 2 20 2 200 Sample Output Case 1: n = 4, m = 10, # lists = 4 Case 2: n = 2, m = 20, # lists = 100 Case 3: n = 2, m = 200, # lists = 10000 题意解析:给定n和m,在整数1~m中选出n个数a1~an,满足条件:1<=a[i]<=m且a[i+1]>=a[i]*2,的序列有多少种。 思路:设dp[i][j]表示长度为i的序列,以j结尾.            初始状态是dp[1][j]=1(1<=j<=m);           对于2<=i<=n,dp[i][j]=sum(dp[i-1][k]),1<=k<=j/2,表示长度为i,以j结尾的序列可能数等于 长度为i-1,以小于等于j/2结尾的序列可能数的和。            最后所求的就是sum(dp[n][i]),1<=i<=m. 代码如下: #include<iostream> #include<cstring> using namespace std; const int MAXN=11; const int MAXM=2001; long long dp[MAXN][MAXM]; int main() { int t,n,m; cin>>t; int cnt=1; while(t--) { cin>>n>>m; memset(dp,0,sizeof(dp)); for(int i=1;i<=m;i++) dp[1][i]=1; for(int i=2;i<=n;i++) { for(int j=1;j<=m;j++) { for(int k=1;k<=j/2;k++) { dp[i][j]+=dp[i-1][k]; } } } long long sum=0; for(int i=1;i<=m;i++) { sum+=dp[n][i]; } cout<<"Case "<<cnt<<": n = "<<n<<", m = "<<m<<", # lists = "<<sum<<endl; cnt++; } return 0; }

上一篇:单链表的逆置
下一篇:属性服务接口与使用

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。