2014-2015 ACM-ICPC, NEERC, Eastern Subregional Contest Problem G. The Debut Album

题目来源：http://codeforces.com/group/aUVPeyEnI2/contest/229669

时间限制：1s

空间限制：64MB

题目大意：给定n，a，b的值

求一个长度为n的由1和2组成的数列，要求数列中最多有a个连续的1和b个连续的2,问由多少种不同的数列

样例：

题目解法：

动态规划，使用一个二维数组，dp[i][1]代表当前位为1的前i个数的排列个数，dp[i][2]代表当前位为2的前i个数的排列个数

代码：

#include <bits/stdc++.h>

#define maxn 51000

#define ll long long

using namespace std;

ll dp[maxn][3]={0};

const int  modd=1e9+7;

int main() {

	int n,a,b;

	cin>>n>>a>>b;

	dp[0][1]=1;

	dp[0][2]=1;

	for(int i=1;i<=n;i++)

	{

		for(int j=1;i-j>=0&&j<=a;j++)

			dp[i][1]=(dp[i][1]+dp[i-j][2])%modd;

		for(int j=1;i-j>=0&&j<=b;j++)

			dp[i][2]=(dp[i][2]+dp[i-j][1])%modd;

		//cout<<dp[i][1]<<" "<<dp[i][2]<<endl;

	}

	ll ans=(dp[n][1]+dp[n][2])%modd;

	cout<<ans<<endl;

	return 0;

}

巴特西

2014-2015 ACM-ICPC, NEERC, Eastern Subregional Contest Problem G. The Debut Album

最新文章

热门文章