【链接】

【题意】

序列中不能连续出现k1个以上的1以及不能连续出现k2个以上的2,然后一共有n1个1以及n2和2,要求这n1+n2个数字都出现.

问序列有多少种可能.

【题解】

这题其实可以转化一下思路。

看成是两个人在轮流给空串后面添加1,2字符串。

第一个人添的是重复的"1",第二个人是重复的"2"

然后第一个人添加的"1"的个数不能超过k1,第二个人添加的"2"("1")的个数不能超过k2.

直到填满为止.

这样第一个人能添加的个数为1..k1之间,第二个人能添加的个数也为1..k2之间.

一个dp的雏形就诞生了。

dp[i][j][p]表示1还剩i个,2还剩j个,然后现在轮到 p=0?第一个人添加:第二个人添加 的方案数目.

(同一个状态可以包括多个字符串,但是不影响)

逆序枚举i,j然后i-l,j,1-p和i,j-l,1-p就分别表示下一个状态了.

(逆序枚举i,j的话,能保证当前算出来的i,j是最终的i,j不是中间结果)

最后输出dp[0][0][0]+dp[0][0][1]就Ok

【代码】

import java.util.Scanner;public class Main {        public static int N = 100;    public static int MOD = 100000000;        public static int n1,n2,k[];    public static int dp[][][];        public static void main(String[] args) {        Scanner in = new Scanner(System.in);        dp = new int[N+5][N+5][2];        k = new int[2];                n1 = in.nextInt();n2 = in.nextInt();k[0] = in.nextInt();k[1] = in.nextInt();                dp[n1][n2][0] = dp[n1][n2][1] = 1;                for (int i = n1;i >= 0;i--)            for (int j = n2;j >= 0;j--) {                for (int l = 1;l <= k[0];l++)                    if (i-l>=0)                        dp[i-l][j][1] = (dp[i-l][j][1] + dp[i][j][0])%MOD;                for (int l = 1;l <= k[1];l++)                    if (j-l>=0)                        dp[i][j-l][0] = (dp[i][j-l][0] + dp[i][j][1])%MOD;            }        int ans = (dp[0][0][0] + dp[0][0][1])%MOD;        System.out.println(ans);    }}