2039: [蓝桥杯2022初赛] 李白打酒加强版 （动态规划）

 

题目描述

话说大诗人李白，一生好饮。幸好他从不开车。
一天，他提着酒壶，从家里出来，酒壶中有酒 2 斗。他边走边唱：
无事街上走，提壶去打酒。
逢店加一倍，遇花喝一斗。
这一路上，他一共遇到店 N 次，遇到花 M 次。
已知最后一次遇到的是花，他正好把酒喝光了。
请你计算李白这一路遇到店和花的顺序，有多少种不同的可能？
注意：壶里没酒( 0 斗) 时遇店是合法的，加倍后还是没酒；但是没酒时遇花是不合法的。

输入格式

输入包含多组测试数据。
第一行为T，表示存在T组测试数据，T不超过30。
对于每组测试数据，输入两个整数N 和M.
1 ≤ N, M ≤ 100。

输出格式

输出一个整数表示答案。由于答案可能很大，输出模1000000007 的结果。

输入样例 复制

1
5 10

输出样例 复制

14

最开始是没写出来的，想的是深度优先搜索，也就是第二个代码，不能AC，后面看别人的推荐，才知道闫学灿（y总）（acwing网站的创始人，开了很多课，我相信有必要去看一看，慢慢的把数据结构学了，也得准备CCF的CSP认证了），看了他讲的蓝桥杯初赛，才搞懂了，从侧面也能看出，我很弱，emm，确实，革命尚未成功，我得继续努力。

分析：

状态设计：dp[i][j][k]的值表示遇到i家店，j朵花，酒壶中还剩k斗酒的可能情况数；
    状态转移方程：dp[i][j][k]=dp[i-1][j][k/2](i>1&&k%2==0) + dp[i][j-1][k+1](j>1);
    边界设计：除了dp[0][0][2]=1，其他元素全为0；
    他一共遇到店 N 次，遇到花 M 次。已知最后一次遇到的是花， 他正好把酒喝光了；所以
    最后一次肯定遇到的是花，那么最后的结果便是dp[N][M-1][1];
    并且酒壶中酒的容量不能超过M；

/**
    再编码：
    状态设计：dp[i][j][k]的值表示遇到i家店，j朵花，酒壶中还剩k斗酒的可能情况数；
    状态转移方程：dp[i][j][k]=dp[i-1][j][k/2](i>1&&k%2==0) + dp[i][j-1][k+1](j>1);
    边界设计：除了dp[0][0][2]=1，其他元素全为0；
    他一共遇到店 N 次，遇到花 M 次。已知最后一次遇到的是花， 他正好把酒喝光了；所以
    最后一次肯定遇到的是花，那么最后的结果便是dp[N][M-1][1];
    并且酒壶中酒的容量不能超过M；

*/

#include <cstdio>
#include <cstring>
using namespace std;

const int mod=1000000007;

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        int dp[n+1][m+1][m+1];
        memset(**dp,0,sizeof(dp));
        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)
                {
                    int &val=dp[i][j][k];
                    if(i>=1&&k%2==0)
                        val=(val+dp[i-1][j][k/2])%mod;
                    if(j>=1)
                        val=(val+dp[i][j-1][k+1])%mod;
                }

        printf("%d\n",dp[n][m-1][1]);
    }
    return 0;
}

 DFS解决
    只能AC 13%，不得不说，对于一个问题，不能找到正确的算法策略与正确的算法策略
    比较，可谓是天壤之别；

/**
    DFS解决
    只能AC 13%，不得不说，对于一个问题，不能找到正确的算法策略与正确的算法策略
    比较，可谓是天壤之别；
*/
#include <iostream>
#include <cstdio>
using namespace std;
const int mod=1000000007;
void drink_DFS(int store,int flow,int drink);
int sum=0,N,M;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        sum=0;
        scanf("%d%d",&N,&M);
        drink_DFS(0,0,2);
        printf("%d\n",sum);
    }
    return 0;
}

void drink_DFS(int store,int flow,int drink)
{
    if(drink < 0) return;
    if(store > N || flow >= M) return;
    if(drink>M) return;
    if(store==N&&flow==M-1&&drink==1)
    {
        sum+=1;
        sum%=mod;
        return;
    }

    drink_DFS(store+1,flow,2*drink);
    drink_DFS(store,flow+1,drink-1);
//    store+=1;
//    drink*=2;
//    drink_DFS(store,flow,drink);
//    store-=1;
//    drink/=2;
//    flow+=1;
//    drink-=1;
//    drink_DFS(store,flow,drink);
//    flow-=1;
//    drink+=1;
}