南沙企业网站建设,齐河建设局网站,汽车用品东莞网站建设,wordpress幻灯片模板4408. 李白打酒加强版 - AcWing题库
题目描述 题目分析
对于这题我们发现有三个变量#xff0c;店#xff0c;花#xff0c;酒的数量#xff0c;对于这种范围我们使用DP来进行分析。
dp[i][j][k]我们表示有i个店#xff0c;j朵花#xff0c;k单位酒的集合#xff0c…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]就一定为最后遇花的方案数
因为已知最后一次遇到的是花他正好把酒喝光了遇一次花喝一次酒酒的数量枚举到和花一样多即可
#includebits/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;
}
