巧克力蛋糕 DP
题目大意,现在有一个L高度的容器,还有三种巧克力:1.高1cm的黑巧克。2.高1cm的白巧克。1.高kcm的黑巧克。然后要使得最上层和最底层都是黑巧克力,并且黑白巧克力必须间隔着放置。可以不放满,但是总高度不能超过L,问:有多少种摆放方式。刚开始我是用dfs跑的,然后tle了。然后看了一下题解发现是dp(题解说是简单dp,但是我看了很久才懂)。我们使用一个二维数组dp[max][5],其中...
·
题目大意,现在有一个L高度的容器,还有三种巧克力:1.高1cm的黑巧克。2.高1cm的白巧克。1.高kcm的黑巧克。然后要使得最上层和最底层都是黑巧克力,并且黑白巧克力必须间隔着放置。可以不放满,但是总高度不能超过L,问:有多少种摆放方式。
刚开始我是用dfs跑的,然后tle了。然后看了一下题解发现是dp(题解说是简单dp,但是我看了很久才懂)。
我们使用一个二维数组dp[max][5],其中dp[i][1/2/3]表示第i层的1cm的黑巧克力/白巧克力/kcm的黑巧克力的可摆放方案数。模拟着题目要求进行dp即可。因为顶上和底下都必须是黑巧克力,最后只需将所有高度的黑巧克力的方案数全加起来即可。
ll dp[1005][5];
int main()
{
ll l, k;
cin >> l >> k;
ll ans = 0;
dp[1][1] = 1;
dp[1][3] = (l >= k) ? 1 : 0;
for (int i = 2; i <= l; i++)
{
if (i - k >= 1)
dp[i][2] = dp[i - 1][1] + dp[i - k][3];
else
dp[i][2] = dp[i - 1][1];
dp[i][1] = dp[i - 1][2];
if (i + k - 1 <= l)
dp[i][3] = dp[i - 1][2];
}
for (int i = 1; i <= l; i++)
ans += dp[i][1] + dp[i][3];
cout << ans << endl;
}
更多推荐
已为社区贡献4条内容
所有评论(0)