DP基础

求方案数

这类问题大的明显特定是，给几个参数，然后要求方案数的个数

E1-走楼梯

蓝桥杯省赛无忧班（C&C++ 组）第 1 期 - 破损的楼梯 - 蓝桥云课 (lanqiao.cn)

经典走楼梯问题的变形，每次走1步，或者2步，但破损的楼梯不能走，求总方案数

cin>>n>>m;
for(int i = 0 ; i < m ; i ++){
    int p;cin>>p;
    broken[p] = true;
}
dp[0] = 1;
if(!broken[1]) dp[1] = 1;
for(int i = 2 ; i <= n ; i ++){
    if(!broken[i]) dp[i] = (dp[i-1] + dp[i-2])%MOD;
}
cout<<dp[n];

E2-求方案数

蓝桥杯省赛无忧班（C&C++ 组）第 1 期 - 建造房屋 - 蓝桥云课 (lanqiao.cn)

给n条街道，每个街道上可以建m个房屋，一共要建k个房屋（在每条街道上，至少建一个房屋），求总方案数

注意，根据样例，可以知道这题不区分一条街道上房屋的位置。

cin>>k>>n;
for(int i = 0 ; i <= k ; i ++){
    dp[0][i] = 1;
}
// dp i j 表示 对前i条街道, 房屋数量为j的方案数量
for(int i = 1 ; i <= n ; i ++){
    //总预算j
    for(int j = i ; j <= k ; j ++){
        // 设第i条街道可能建了r个房屋
        for(int r = 1 ; r <= m && j-r >= i-1 ; r ++){
            dp[i][j] = (dp[i][j] + dp[i-1][j-r]) % MOD;
        }
    }
}
cout<<dp[n][k];

E4-求方案数

蓝桥杯省赛无忧班（C&C++ 组）第 1 期 - 可构造的序列总数 - 蓝桥云课 (lanqiao.cn)

求满足如下关系的序列总方案个数：

• 序列的长度为 n
• 1≤a1≤a2≤a3≤......≤an≤k
• ai 是 ai−1的倍数（ i≥2i≥2 ）

总长度为n，元素至少大于等于1，从左到右依次是上一个元素的倍数。

dp{i，k}就表示长度为n时，小于k的方案数量。

从小到大遍历，遍历当前元素的倍数的每个，叠加方案数即可。

cin>>k>>n;
for(int i = 1 ; i <= k ; i ++){
    dp[1][i] = 1;
}
for(int i = 2 ; i <= n ; i ++){
    for(int j = 1 ; j <= k ; j ++){
        for(int r = 1 ; r*r <= j; r ++){
            if(r*r == j){ //两个因子相同，去重
                dp[i][j] = (dp[i][j]+dp[i-1][r])%MOD;
            }else if (j % r == 0){
                dp[i][j] = (dp[i][j]+dp[i-1][r]+dp[i-1][j/r])%MOD;
            }
        }
    }
}
for(int i = 1 ; i <= k ; i ++){
    ans = (ans + dp[n][i]) % MOD;
}
cout<<ans;

E5-求方案数

蓝桥杯省赛无忧班（C&C++ 组）第 1 期 - 安全序列 - 蓝桥云课 (lanqiao.cn)

有n个空位，放任意数量个酒桶，每2个酒桶需要间隔k个位置，求总方案数

从小到大遍历空位数量i，空位数量为i的方案数 == i不放酒桶的方案数 + i放酒桶的方案数

== i-1个位置的方案数 + i-k-1个位置的方案数( i-k-1 >= 0 , 否则为1)

cin>>n>>k;
dp[0] = 1;
for(int i = 1 ; i <= n ; i ++){
    if(i-k-1 >= 1){
        dp[i] = (dp[i-1] + dp[i-k-1]) % MOD;
    }else{
        dp[i] = (dp[i-1] + 1) % MOD;
    }
}
cout<<dp[n];

E6-求方案数

1.摆花 - 蓝桥云课 (lanqiao.cn)

有n种花，需要摆放m盆，每种花最多摆放a[i]盆，求总方案数。

设dp{i, k} 为前i种花，摆放k盆的总方案数量。

int main(void){
	cin>>n>>m;
	for(int i = 1 ; i <= n ; i ++){
		cin>>a[i];
	}
	dp[0] = 1;
	for(int i = 1 ; i <= n ; i ++){
		for(int j = m ; j >= 0 ; j --){
            //注意若使用1维数组，这里的r需要从1开始，避免重复累加DP[j]
			for(int r = 1 ; r <= a[i] ; r ++){
				if(j - r >= 0) dp[j] = (dp[j] + dp[j - r])%MOD;
			}
		}
	}
	cout<<dp[m];
	return 0;
}

E6-异或运算

给n个数和一个数x，求子序列中异或和为x的个数。

设DP{i，j} 表示前i个数，异或和为j的方案总数。

DP{i，j} 包含两种解，一种不包含a[i], 一种包含a[i], 因此，有 DP{i，j} = DP{i-1, j} + DP{i-1, j ^ a[i]}。

（假设j中已经包含了a[i]，又有j ^ a[i] ^ a[i] == j，所以相当于从j这个和中消去了a[i]）

//异或预算的特点：

//任何数异或0，都等于自身；
//任何数异或1，都等于自身取反；
//任何数异或自身，都等于0；（注意是a ^ a，与上文的^a不同）；
//任何数对同一个数异或两次后，都等于自身

cin>>n>>x;
for(int i = 1 ; i <= n ; i ++){
    cin>>a[i];
}
dp[0][0] = 1;
now = 1; //滚动数组优化
for(int i = 1 ; i <= n ; i ++){
    for(int j = 0 ; j < 64 ; j ++){
        dp[now][j] = (dp[now^1][j] + dp[now^1][j^a[i]]) % MOD;
    }
    now ^= 1;
}
cout<<dp[now^1][x];

求最优解

E1-数字三角形

1.数字三角形 - 蓝桥云课 (lanqiao.cn)

给一个n列的数字三角形，要从上走到下，并且左右步数之差不超过1，要求总和最大的路径。

这题是基本的数字三角形的变形，由于左右步数之差不超过1，路径结尾一定落在最后一行的中位数列上，所以我们只需要考虑中位数列。

cin>>n;
for(int i = 1 ; i <= n ; i ++){
    for(int j = 1 ; j <= i ; j ++){
        cin>>a[i][j];
    }
}
for(int i = 1 ; i <= n ; i ++){
    for(int j = i ; j >= 1 ; j --){
        if(j-1 >= 1) dp[j] = max(dp[j], dp[j-1]) + a[i][j];
        else dp[j] = dp[j] + a[i][j];
    }
}
if(n & 1){
    cout<<dp[n/2+1];
}else{
    cout<<max(dp[n/2], dp[n/2+1]);
}

E2-LIS变形

蓝桥杯省赛无忧班（C&C++ 组）第 1 期 - 拍照 - 蓝桥云课 (lanqiao.cn)

给一个长度为n的序列，求一个位置P，从P往左走，删除元素，使得其上升；从P往右边走，删除元素，使其下降。位置P需要删除的元素是最少的。

这题是最长上升子序列问题的变形。从左到右，从右到左，分别求一次最长不下降子序列。然后遍历求最值。

cin>>n;
for(int i = 1 ; i <= n ; i ++){
    cin>>a[i];
    dpL[i] = dpR[i] = 1;
}
for(int i = 1 ; i <= n ; i ++){
    for(int j = i-1 ; j >= 1 ; j--){
        if(a[i] >= a[j]){
            dpL[i] = max(dpL[i], dpL[j] + 1);
        }
    }
}
for(int i = n ; i >= 1 ; i --){
    for(int j = i+1 ; j <= n ; j ++){
        if(a[i] >= a[j]){
            dpR[i] = max(dpR[i], dpR[j] + 1); 
        }
    }
}
ans = INT_MAX;
for(int i = 1 ; i <= n ; i ++){
    ans = min(ans, n - (dpL[i] + dpR[i] - 1) );
}
cout<<ans;

E3-最大区间和

给一个长度为n的数列， 求最大区间和（结果必须大于等于0）

cin>>n;
v.resize(n);
for(int i = 0 ; i < n ; i ++){
    cin>>v[i];
}
int sum = 0;
int l = 0;
int r = 0;
int max_ = -1;
//每个区间都可以看作是 最后一个数 + 前n个数
//此处使用sum记录，往前加多少个数是最优的
for(int i = 0 ; i < n ; i ++){
    if(sum + v[i] < 0){
        sum = 0;
        l = i+1;
    }else{
        sum += v[i];
        r = i+1;
        if(sum > max_){
            max_ = sum;
        }
    }
}
if(max_ == -1) max_ = 0;
cout<<max_;

多维DP

E1-图上DP

蓝桥杯省赛无忧班（C&C++ 组）第 1 期 - 地图 - 蓝桥云课 (lanqiao.cn)

给一张长为n，宽为m的矩阵图，可以从上到下，或者从左到右走，但是最多旋转k次，

求从（1，1）走到（n，m）的路径个数

dp{i,j,t,p} 表示 走到i，j为止，旋转了k次，此时方向为p的方案个数

cin>>n>>m>>k;
for(int i = 1 ; i <= n ; i ++){
    for(int j = 1 ; j <= m ; j ++){
        cin>>road[i][j];
    }
}
//初始化边界
dp[1][1][0][0] = dp[1][1][0][1] = 1;
for(int i = 2 ; i <= n ; i ++){
    if(road[i][1] == '.'){
        dp[i][1][0][1] = dp[i-1][1][0][1];
    }
}
for(int i = 2 ; i <= m ; i ++){
    if(road[1][i] == '.'){
        dp[1][i][0][0] = dp[1][i-1][0][0];
    }
}
for(int i = 2 ; i <= n ; i ++){
    for(int j = 2 ; j <= m ; j ++){
        for(int t = 1 ; t <= k ; t ++){
            //每个位置的DP都可以由四个状态转移而来
            if(road[i][j] == '.'){
                dp[i][j][t][0] = dp[i][j-1][t-1][1] + dp[i][j-1][t][0];
                dp[i][j][t][1] = dp[i-1][j][t][1] + dp[i-1][j][t-1][0];
            }
        }
    }
}
for(int i = 0 ; i <= k ; i ++){
    ans += dp[n][m][i][0] + dp[n][m][i][1];
}
cout<<ans;

01背包

E1-01背包变形

蓝桥杯省赛无忧班（C&C++ 组）第 1 期 - 最快洗车时间 - 蓝桥云课 (lanqiao.cn)

给n辆车，每辆车要洗\(t_i\)时间，有两个洗车机器，可以同时运行，求全部洗好需要的时间。

这题是背包问题，设背包的容量为sum/2，求背包的最大价值即可。

cin>>n;
for(int i = 1 ; i <= n ; i ++){
    cin>>a[i];
    sum += a[i];
}
for(int i = 1 ; i <= n ; i ++){
    for(int j = sum/2 ; j >= a[i] ; j --){
        dp[j] = max(dp[j], dp[j - a[i]] + a[i]);
    }
}
cout<<sum - dp[sum/2];

另一种写法

cin>>n;
for(int i = 1 ; i <= n ; i ++){
    cin>>a[i];
    sum += a[i];
}
dp[0] = true;
//求其中一个机器可能的时间方案
for(int i = 1 ; i <= n ; i ++){
    for(int j = sum ; j >= a[i] ; j --){
        dp[j] = (dp[j] | dp[j - a[i]]);
    }
}
//输出答案
ans = INT_MAX;
for(int i = 0 ; i <= sum/2 ; i++){
    if(dp[i]) ans = min(sum - i,ans);	
}
cout<<ans;

E2-01背包变形

蓝桥杯省赛无忧班（C&C++ 组）第 1 期 - 电影放映计划 - 蓝桥云课 (lanqiao.cn)

给N部电影，总共播放时间是M分钟，每部电影间至少间隔k分钟，给每部电影的分钟数t_i和利润p_i，

每部电影可以重复播放，要求最大利润。

每部电影至少间隔k分钟，只需要给每个\(t_i\)和m都加上k，然后转化为普通完全背包问题即可。

cin>>m>>n;
for(int i = 1 ; i <= n ; i ++){
    cin>>t[i]>>p[i];
}
cin>>k;
for(int i = 1 ; i <= n ; i ++){
    t[i] += k;
}
m += k;
for(int i = 1 ; i <= n ; i ++){
    for(int j = t[i] ; j <= m ; j ++){
        dp[j] = max(dp[j], dp[j-t[i]] + p[i]);
        ans = max(ans, dp[j]);
    }
}
cout<<ans;

E3-多维01背包

1.背包与魔法 - 蓝桥云课 (lanqiao.cn)

与普通背包问题不同的是，可以进行对物品1次变形：增加重量k，价值翻倍。

需要增加一个维度，dp[j][r]表示重量j下进行r次变形的最大重量。

for(int i = 1 ; i <= n ; i ++){
    for(int j = m ; j >= w[i] ; j --){
        dp[j][0] = max(dp[j][0], dp[j - w[i]][0] + v[i]);
        dp[j][1] = max(dp[j][1], dp[j - w[i]][1] + v[i]);
        if(j >= w[i] + k) dp[j][1] = max(dp[j][1], dp[j - w[i] - k][0] + 2*v[i]);
    } 
}
cout<<max(dp[m][1], dp[m][0]);

E4-01背包变形

蓝桥杯省赛无忧班（C&C++ 组）第 1 期 - 倒水 - 蓝桥云课 (lanqiao.cn)

有m升水，n个客人，

对于第i个客人，不倒水，得到ei满意度；倒ai升的水，得到bi满意度；倒ci升的水，得到di满意度；

求最高的满意度。

这题相当于在01背包的基础上增加了更多选择，本质一样。

for(int i = 1 ; i <= n ; i ++){
    for(int j = m ; j >= 0 ; j --){
        ll x1,x2,x3;
        x1 = dp[j] + e[i];
        x2 = x3 = LONG_LONG_MIN;
        if(j >= a[i]) x2 = dp[j - a[i]] + b[i];
        if(j >= c[i]) x3 = dp[j - c[i]] + d[i];
        dp[j] = max(x1,max(x2,x3));
    }
}
cout<<dp[m];

E5-01背包+排序

1.蓝桥课程抢购 - 蓝桥云课

给n个课程，每个课程有持续时间t和价值p，每个课程有截止时间d，必须在d之前做完。

相比普通的01背包，增加了截止时间d。

更新区间从[t, m]，变为[t, d]，注意需要对d进行排序，保证先考虑d小的课程。

sort

struct task{
	ll t,d,p;
	bool operator<(const task & rhs){
		return d < rhs.d;
	}
}a[N];

main

sort(a+1,a+1+n);
for(int i = 1 ; i <= n ; i ++){
    for(int j = a[i].d ; j >= a[i].t ; j --){
        dp[j] = max(dp[j], dp[j - a[i].t] + a[i].p);
        ans = max(dp[j], ans);
    }
}

E6-01最小背包

蓝桥杯省赛无忧班（C&C++ 组）第 1 期 - 购物策略 - 蓝桥云课 (lanqiao.cn)

给n个物品，每个物品需要花t个时间来购买，在每个物品的购买期间，每过1个单位时间，就可以免费获得另外的1个商品，求最小花销。

这题的限制不是体积，而是数量，我们可以把背包的容量当成是某个数量，买每个物品消耗的数量为t[i] + 1,

然后就可以转化为求： 背包体积至少为n的最小花销。

cin>>n;
for(int i = 1 ; i <= n ; i ++){
    cin>>t[i]>>c[i];
    t[i]++;
}
for(int i = 1 ; i <= n ; i ++){
    dp[i] = INF;
}
dp[0] = 0;
for(ll i = 1 ; i <= n ; i ++){
    for(ll j = n; j >= 0 ; j --){
        dp[j] = min(dp[j], dp[max(0ll, j - t[i])] + c[i]);
    }
}
cout<<dp[n];