你有三种盘子，黑薄，白薄，黑厚。

薄的盘子占1，厚的盘子占k。

有一个高度为L的桶，盘子总高度不能超出桶的总高度（可以小于等于）。相同颜色的盘子不能挨着放。

问桶内装盘子的方案数。

 

如 L = 5，k = 3时的方案数为6（下图）

 

Sample Input15 3Sample Output 16Sample Input 29 10Sample Output 25Sample Input 310 10Sample Output 36Sample Input 420 5Sample Output 486Sample Input 5100 2Sample Output 53626169232670

　　

 

 

 

 

很简单的DP。

注意好 k 和当前枚举到的位置的关系。

f[i][1]表示黑薄，f[i][2]白薄，f[i][3]黑厚。 

 

 

#include 
     
      #include 
      
       #include 
       
        using namespace std;typedef long long LL;const int maxn = 100+100;LL f[maxn][4];int main(){    int l, k;    scanf("%d%d", &l, &k);    f[1][1] = 1;    f[1][3] = (k <= l ? 1 : 0);        for (int i = 2; i <= l; i++)    {        f[i][1] = f[i-1][2];        f[i][2] = f[i-1][1] + (i-k > 0 ? f[i-k][3]:0);        if (l-i+1 >= k)            f[i][3] = f[i-1][2];    }    LL ans = 0;    for (int i = 1; i <= l; i++)        ans += f[i][1] + f[i][3];    printf("%lld\n", ans);}