蓝桥杯每日一题2023.9.27

4408. 李白打酒加强版 - AcWing题库

题目描述

题目分析 

对于这题我们发现有三个变量,店,花,酒的数量,对于这种范围我们使用DP来进行分析。

dp[i][j][k]我们表示有i个店,j朵花,k单位酒的集合,其属性为数量

我们需要不重不漏将此分为两类进行dp,

第二类为最后是店dp[i - 1][j][k / 2]

        条件:i >= 1(因为如果当前店数为0,之前一定没有遇过店,-1为负也不正确)

                   k % 2 == 0 (k可以被2整除,因为遇到店前必须为2的倍数才能/2)

第一类为最后是花dp[i][j - 1][k + 1] 

        条件:j >= 1 (同理)(k + 1遇花可以使其-1变成k)

注:最后输出时不能是dp[n][m][0],因为这样不能分清楚最后是遇花还是遇店,而且这样算无论遇花还是遇店的方案数都是一样的,所以输出dp[n][m - 1][1]就一定为最后遇花的方案数

因为已知最后一次遇到的是花,他正好把酒喝光了,遇一次花喝一次酒,酒的数量枚举到和花一样多即可文章来源地址https://www.uudwc.com/A/jrzO8/

#include<bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
const int N = 101;
int n, m, dp[N][N][N];
int main()
{
	cin >> n >> m;
	dp[0][0][2] = 1;
	for(int i = 0; i <= n; i ++)//店 
	{
		for(int j = 0; j <= m; j ++)//花 
		{
			for(int k = 0; k <= m; k ++)//酒 
			{
				if(i >= 1 && k % 2 == 0)//遇店 
				{
					dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k / 2]) % mod; 
				}
				if(j >= 1)//遇花 
				{
					dp[i][j][k] = (dp[i][j][k] + dp[i][j - 1][k + 1]) % mod;
				}
			}
		}
	}
	cout << dp[n][m - 1][1]; 
	return 0;
}

原文地址:https://blog.csdn.net/m0_75087931/article/details/133347299

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请联系站长进行投诉反馈,一经查实,立即删除!

h
上一篇 2023年10月08日 12:15
下一篇 2023年10月08日 14:15