【动态规划】sicily1011

1011. Lenny's Lucky Lotto

题目大意：

给定正整数n, m，构建的列表满足下列条件：

1. 列表长度为n
2. 列表的第i个数不能超过2的i次方
3. 列表的最后一个数不能超过m

求出这样的列表的最大数目。

 

解题思路：

1. 一般遇到需要求最优解的，应该立马想到动态规划；
2. 影响列表的数目的应该是有两个状态，一个是列表的长度，一个是列表的末尾值。因此采用两个状态，申请表dp[11][2001]。其中dp[i][j]表示：当长度为i，末尾为j的列表的数目。
3. 状态转移方程：

dp[i][j] = dp[i][j-1] + dp[i-1][j/2]

很容易理解这个状态方程。

 

初始化状态当然是dp[1][i] = i，加上一些必要的剪支，列表的第i个数一定是大于2的i次方并且要小于（m / 2^(n-i)）的，自己可以证明。

一开始疏忽了，没有使用long long类型，WA几次之后发现数字过大时，可能出现负数，使用printf打印long long时是采用%lld的格式。

 

原题目见底下附带。

代码如下：

 

/*
 * main.cpp
 *
 *  Created on: Sep 23, 2011
 *      Author: raphealguo（ rapheal.iteye.com）
 */

#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;

#define N 11
#define M 2001
long long dp[N][M];//dp[i][j] 表示n=i m=j时的最大Luck list数目
int n, m;

void solve(){
	//动态规划
	int i, j;

	for (i = 1; i <= m; ++i){//初始化
		dp[1][i] = i;
	}
	for (i = 2; i <= n; ++i){
		for (j = 1<<(i-1); j*(1<<(n-i)) <= m; ++j){//必要作出一些剪支，减少运算
			dp[i][j] = dp[i][j-1] + dp[i-1][j/2];
		}
	}
}

int main(){
	int t, c = 1;
	scanf ("%d", &t);

	while (t--){
		memset(dp, 0, sizeof(dp));
		scanf ("%d %d", &n, &m);

		solve();

		printf("Case %d: n = %d, m = %d, # lists = %lld\n", c++, n, m, dp[n][m]);
	}

	return 0;
}

 

 

附带原题目：

1011. Lenny's Lucky Lotto

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