首页 > 代码库 > Sicily 1146:Lenny's Lucky Lotto(dp)

Sicily 1146:Lenny's Lucky Lotto(dp)

  题意:给出N,M,问有多少个长度为N的整数序列,满足所有数都在[1,M]内,并且每一个数至少是前一个数的两倍。例如给出N=4, M=10, 则有4个长度为4的整数序列满足条件: [1, 2, 4, 8], [1, 2, 4, 9], [1, 2, 4, 10], [1, 2, 5, 10]

     分析:可用动态规划解题,假设dp[i][j],代表满足以整数i为尾数,长度为j的序列的个数(其中每一个数至少是前一个数的两倍)。那么对于整数i,dp[i][j] 等于所有dp[k][j-1]的和,其中k满足:2*k <= i。计算出dp矩阵后,答案便是dp[i][N]的和(i = 1, 2, ... ,N)

技术分享

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[])
{
    int T;
    int index = 0;
    cin >> T;
    while(T--){
        int N, M;
        cin >> N >> M;
        long long dp[M+1][N+1];
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= M; i++){
            for(int j = 1; j <= N; j++){
                if(j == 1)dp[i][j] = 1;
                else{
                    for(int k = 1; 2*k <= i; k++){
                        dp[i][j] += dp[k][j-1];
                    }
                }
                
            }
        }
        long long ans = 0;
        for(int i = 1; i <= M; i++){
            ans += dp[i][N];
        }
        printf("Case %d: n = %d, m = %d, # lists = %lld\n", ++index, N, M, ans);
    }
    return 0;
}

 

Sicily 1146:Lenny's Lucky Lotto(dp)