首页 > 其他 > 详细

FZU 2098 刻苦的小芳

时间:2016-03-16 08:23:27      阅读:118      评论:0      收藏:0      [点我收藏+]

这个问题转化一下就是求长度为2*n的正确括号匹配串,两个匹配的括号之间的距离不超过2*k的有几种。

假设左括号为1,右括号为-1,dp[i][j]表示长度为i的括号匹配串,前缀和为j的有几种。dp[2*n][0]就是答案。

递推式:

if (j + 1 <= k) dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % MOD;
if (j - 1 >= 0) dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MOD;

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

const int MOD=1e9+7;
int n,k;
int dp[210][105];

void init()
{
    memset(dp,0,sizeof dp);
    dp[0][0] = 1;
    for (int i = 1; i <= 2*n; i++)
    {
        for (int j = 0; j <= k; j++)
        {
            if (j + 1 <= k) dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % MOD;
            if (j - 1 >= 0) dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MOD;
        }
    }
}

int main()
{
    int R=1;
    while(~scanf("%d%d",&n,&k))
    {
        init();
        printf("Case %d: %d\n",R++,dp[2*n][0]);
    }

    return 0;
}

 

FZU 2098 刻苦的小芳

原文:http://www.cnblogs.com/zufezzt/p/5282000.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!