化学品问题--线性dp详细解释

解题思路:

用dp[i][0]记录第i个位置不放那个药品的方案数

dp[i][1]记录第i个位置放药品的方案数
参考代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 35;
typedef long long ll;
ll t,m,n,sum = 0;
int dp[N][5];//dp[i][0]表示第i位不放药品的方案数，dp[i][1]表示第i位放药品的方案数
void solve(){
    sum = 0;
    memset(dp,0,sizeof(dp));
    dp[0][0] = 1;//初始化dp[0][0]为1 当i==m时需要要用到这个情况  先看到后面再回来看 
    //(表示后面连续的m个位置都放药品的方案数为1) 
    dp[1][1] = 1;dp[1][0]=1;//初始化第一位无论放不放那个药都是一种方案 
    //遍历完善dp数组 
    for(int i = 2;i<=n;i++){
        dp[i][0] = dp[i-1][0] + dp[i-1][1];//第i位不放药品的方案数(前面一个放不放都可以)等于前一位
        //放药品的方案数加上不放药品的方案数 
        if(i<m) dp[i][1] = dp[i-1][0] + dp[i-1][1];//i小于m时放药品还不用考虑爆炸 
        else{//i>=m 放药品时要考虑爆炸的可能 
            sum+=dp[i-1][0];//首先加上前一个不放药品(前面一个不妨就不会构成连续的m个)的方案数 
            sum+=dp[i-1][1] - dp[i-m][0] ;//前面一个放了药品，就必须避免这m个都放药品
            //的情况， 他的情况总数应该是这相邻m个的 前一个位置不放药品的方案数
            //例如：1 2 3 4 5；当i = 5,m = 3时，要去掉3 4 5都放药品的方案数；
            //那就是2号位不放药品的方案数 原因--->确定3 4 5位置为1(放了药品)；
            //_ _ 1 1 1 显然 2号为不能再为1，这样的方案数就是2号位为0的方案数 
            //(如果算上了2号位放药品的方案数那么会导致2 3 4成了连续的m个药品) 
            //当i==m的时候 减去这m个都是1(放药品)的方案 应该是1 即1到i都是放药品这一种方案
            //所以先设置dp[0][0] = 1; 
            dp[i][1] = sum;//sum就是第i个放药品的数目 
            sum = 0;//记得清0 
        }
    }
}
int main(){ 
    cin>>t;
    while(t--){
        cin>>n>>m;
        solve();
        cout<<dp[n][0] + dp[n][1] <<endl;
    }        
    return 0;
}