ZOJ 2402 Lenny’s Lucky Lotto Lists (DP)

ZOJ 2402 Lenny’s Lucky Lotto Lists

用1-M之间的数，组成一个长度为N的序列，使得每一个数是之前那个数的二倍以上，如对于N=4，M=10：

1 2 4 8
1 2 4 9
1 2 4 10
1 2 5 10

有四种选择，题目给出的范围是N<=10,M<=2000。

设DP[i][j]表示长度为i的序列结尾为j的情况数，从小往大递推就行了。。

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<sstream>
#include<algorithm>
#include<iomanip>
using namespace std;
long long M,N;
long long DP[ 11 ][ 2001 ];
int main(void)
{
    long long cases,t;
    long long i,j,s,k;
    long long sum;

    N = 10; M = 2000;
    for( i = 1; i <= M; i++ )
            DP[1][i] = 1;
    for( i = 2; i <= N; i++ )
        for( j = 1; j <= M; j++ )
            DP[i][j] = 0;

    for( i = 1; i < N; i++ ){
        for( j = 1; j <= M; j++ )
            if( DP[i][j] )
            for( k = j*2; k <= M; k++ )
                DP[i+1][k] += DP[i][j];
    }
    //以上为预处理。。
    scanf("%lld",&cases);
    for( t = 1; t <= cases; t++ ){
        scanf("%lld%lld",&N,&M);
        for( i = 1,sum = 0; i <= M; i++ )
            sum += DP[N][i];//长度为N的可以有不同的结尾，所以所有的+起来
        printf("Case %lld: n = %lld, m = %lld, # lists = %lld\n",t,N,M,sum);
    }
    return 0;
}