hunnu---11547 你的组合数学学得如何？

解析：比较简单的DP，从左向右一个一个连续着放，dp[X][Y]表示到第X个硬币的时候Y状态的方案数，Y=0表示x左边那个不是正面的，Y=1表示x左边那个是正面

如果左边不是正面，那么当前放正面的就把方案数加到Y=1里面，放反面的就加到Y=0

如果是正面，那么当前放正面就不成立了，所以不用加，放反面就加到Y=0里面去

递推公式：

dp[i][0]= ( dp[i-1][0] + dp[i-1][1] )%mod;

dp[i][1]= dp[i-1][0] %mod;

你的组合数学学得如何？

Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:65536KB

Total submit users: 152, Accepted users: 120

Problem 11547 : No special judgement

Problem description

小明和小红总是喜欢在一起玩。一天，他们又在一起愉快的玩耍了一个下午，到了吃晚饭的时间，他们决定用抛硬币的方法来决定谁请吃晚餐。
规则很简单，他们抛一枚均匀的硬币N次，如果出现连续两次或更多正面朝上的情况，那么就是小红请，否则就是小明请。
现在小明想知道，抛N次的所有情况下，会有多少次不出现连续两次正面或更多正面朝上的情况

Input

有多组测试数据，请处理到文件结束。
每组测试数据仅包含一个数N（1 <= N <= 1000），表示抛掷的次数。

Output

每组数据输出一行,格式为Case #k: Ans, k从1开始, Ans表示答案.
由于答案可能会很大,输出Ans % (10^9 + 7)即可.

Sample Input

1

2

Sample Output

Case #1: 2

Case #2: 3

Problem Source

HUNNU Contest

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#define mod 1000000007

using namespace std;

int main()

{

    int n,i,j,k,l=;

    int dp[][];

    while(cin>>n)

    {

        memset(dp,,sizeof(dp));

        dp[][]=;

        for(i=;i<=n;i++)//从1到n位置一个一个位置去考虑硬币的正反

        {

            dp[i][]=(dp[i-][]+dp[i-][])%mod;

            dp[i][]=dp[i-][]%mod;

        }

        cout<<"Case #"<<l++<<": "<<(dp[n][]+dp[n][])%mod<<endl;

    }

    return ;

}

秒客网

hunnu---11547 你的组合数学学得如何？

相关文章