DP--Aizu1378：Secret of Chocolate Poles

本文主要是介绍DP--Aizu1378：Secret of Chocolate Poles，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Select Of Chocolate Poles 

题意：有一个竖直放置的高度为l cm的盒子，现在有三种方块分别为1cm的白块，1cm的黑块，k cm的黑块，要求第一块放进去的必须是黑色的，盒子最上边的必须也是黑色的，盒子不必放满，问一共有多少种放法。

思路：知道要用DP确实死活推不出状态转移公式来，这就很窒息了。到网上搜了一下题解，，，，，，还是自己太low了。

二维DP，第一维表示盒子的高度，第二维表示当前是放白块还是黑块。0表示白块，1表示黑块即：(白块是不会影响放的种类的数目的)

当高度还不到k cm时：dp[i][0] = dp[i][1], dp[i][1] = dp[i][0] ；

当高度大于k cm时：dp[i][0] = dp[i][1], dp[i][1] = dp[i][0] +dp[i-k][0];

代码：

/*Time:2018/9/7Writer:SykaiFunction:Secret of Chocolate Poles
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <cstring>
#include <queue>
#define INF 0x3f3f3f3f
#define MIN(a,b) a<b ? a : b
#define FRE() freopen("in.txt","r",stdin)
using namespace std;
const int maxn = 110;
const int MOD = 1e9 + 7;
typedef long long ll;
typedef pair<int, int> P;
ll dp[maxn][2];int main(){int l,k;while(scanf("%d%d",&l,&k)!=EOF){dp[0][0] = 1;for(int i = 1; i<=l; i++){dp[i][1] = dp[i-1][0];dp[i][0] = dp[i-1][1];if(i>=k) dp[i][1] = dp[i-1][0]+dp[i-k][0];}ll ans = 0;for(int i = 1; i<=l; i++){ans += dp[i][1];}printf("%lld\n",ans);}return 0;
}

 

这篇关于DP--Aizu1378：Secret of Chocolate Poles的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---