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; }
用int会越界
不会越界吧?