2039: [Bluebridge cup 2022 preliminaries] Li Bai's enhanced version (dynamic planning)

 

Title Description

On the great poet Li Bai , Good drink for life . Fortunately, he never drives .
One day , He's carrying a jug , Come out of the house , There is wine in the wine pot 2 Bucket . He sang as he walked ：
Walk on the street , Pick up the pot and go get the wine .
Double for every shop , Have a drink with flowers .
This way , He met the store N Time , Encounter flowers M Time .
We know that the last time we met was flowers , He just finished his drink .
Please calculate the order of shops and flowers Li Bai meets along the way , How many different possibilities ？
Be careful ： There is no wine in the pot ( 0 Bucket ) Shiyu store is legal , There is still no wine after doubling ; But it's illegal to meet flowers without wine .

Input format

Input contains multiple sets of test data .
First act T, Indicates presence T Group test data ,T No more than 30.
For each group of test data , Enter two integers N and M.
1 ≤ N, M ≤ 100.

Output format

Output an integer for the answer . Because the answer can be big , Output mode 1000000007 Result .

sample input Copy

1
5 10

sample output Copy

14

It was not written at first , Think of depth first search , That is, the second code , You can't AC, See others' recommendations later , Just know Yan xuecan （y total ）（acwing The founder of the website , There are many classes , I believe it is necessary to have a look , Slowly learn the data structure , You have to be prepared CCF Of CSP Certified ）, I watched him talk about the preliminary match of the Blue Bridge Cup , Just understand , It can also be seen from the side , I'm weak ,emm, exactly , The revolution has not yet succeeded , I have to keep trying .

analysis ：

State Design ：dp[i][j][k] The value of indicates that i stores ,j A flower , There is still something left in the wine pot k The number of possible cases of fighting alcohol ;
    State transition equation ：dp[i][j][k]=dp[i-1][j][k/2](i>1&&k%2==0) + dp[i][j-1][k+1](j>1);
    Boundary design ： except dp[0][0][2]=1, All the other elements are 0;
    He met the store N Time , Encounter flowers M Time . We know that the last time we met was flowers , He just finished his drink ; therefore
    The last time I must encounter flowers , Then the final result is dp[N][M-1][1];
    And the volume of wine in the wine pot cannot exceed M;

/**
     Recode ：
     State Design ：dp[i][j][k] The value of indicates that i stores ,j A flower , There is still something left in the wine pot k The number of possible cases of fighting alcohol ;
     State transition equation ：dp[i][j][k]=dp[i-1][j][k/2](i>1&&k%2==0) + dp[i][j-1][k+1](j>1);
     Boundary design ： except dp[0][0][2]=1, All the other elements are 0;
     He met the store  N  Time , Encounter flowers  M  Time . We know that the last time we met was flowers ,  He just finished his drink ; therefore 
     The last time I must encounter flowers , Then the final result is dp[N][M-1][1];
     And the volume of wine in the wine pot cannot exceed 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 solve
    Can only AC 13%, Have to say , For a question , Unable to find the correct algorithm strategy and the correct algorithm strategy
    Compare , It's a big difference ;

/**
    DFS solve 
     Can only AC 13%, Have to say , For a question , Unable to find the correct algorithm strategy and the correct algorithm strategy 
     Compare , It's a big difference ;
*/
#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;
}