首页 > 代码库 > zoj 2402 - Lenny's Lucky Lotto Lists
zoj 2402 - Lenny's Lucky Lotto Lists
题目:一个序列,每个元素都至少的前面的二倍,最大值为n,问长度为l的这种船有多少个。
分析:dp,LIS类似物。
状态:f(i,j)结束数字为j且长度为i的序列的个数,有转移方程:
F[ i ][ j ] = Sum(F[ i-1 ][ k ]) { 2^(i-2)<= k <= j/2);
再用S[ i ][ j ]求出长度为i结束不超过j的串的个数就可以了。
说明:(2011-09-19 01:33).
#include <iostream> #include <cstdlib> #include <cstring> using namespace std; long long F[ 11 ][ 2001 ]; long long S[ 11 ][ 2001 ]; int main() { //打表 memset( F, 0L, sizeof( F ) ); memset( S, 0L, sizeof( S ) ); F[ 0 ][ 0 ] = 1L; for ( int i = 1 ; i <= 10 ; ++ i ) for ( int j = (1<<(i-1)) ; j <= 2000 ; ++ j ) { for ( int k = (1<<(i-1))/2 ; k <= (j>>1) ; ++ k ) F[ i ][ j ] += F[ i-1 ][ k ]; S[ i ][ j ] = S[ i ][ j-1 ] + F[ i ][ j ]; } // int t,n,m; while ( cin >> t ) for ( int c = 1 ; c <= t ; ++ c ) { cin >> n >> m; cout << "Case " << c << ": n = " << n << ", m = " << m << ", # lists = " << S[ n ][ m ] << endl; } return 0; }
zoj 2402 - Lenny's Lucky Lotto Lists
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。