《算法竞赛进阶指南》0x51 线性DP

0x51 线性DP

271. 杨老师的照相排列

题意：

$N$ 个人站成左端对齐的 $k$ 排，每排有 $N_i$ 人，$N_i>N_j$ 如果 $i<j$，则 $N_i>N_j$ 。每一排从左到右身高递减，每一列从后到前身高递减。询问方案数。

解析：

按照身高从大到小的顺序决定位置。在任意时刻，已经确定位置的人在每一行中一定是从左开始的连续位置。

用 $k$ 元组可以描述当前已经确定的位置。在决定当前人的位置时，可放的排为没放满的排，且放完后满足 $n_i>n_j(i<j)$，$n_i$ 为第 $i$ 排已经放的人数。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 32;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;int n[6];
int k; 
ll dp[maxn][maxn][maxn][maxn][maxn];
int check(int a, int b, int c, int d, int e){return a >= b && b >= c && c >= d && d >= e && e >= 0;
}
void solve(){memset(dp, 0, sizeof(dp));dp[0][0][0][0][0] = 1;for(int a = 0; a <= n[1]; a++){for(int b = 0; b <= n[2]; b++){for(int c = 0; c <= n[3]; c++){for(int d = 0; d <= n[4]; d++){for(int e = 0; e <= n[5]; e++){if(!check(a, b, c, d, e))continue;if(check(a-1, b, c, d, e))dp[a][b][c][d][e] += dp[a-1][b][c][d][e];if(check(a, b-1, c, d, e))dp[a][b][c][d][e] += dp[a][b-1][c][d][e];if(check(a, b, c-1, d, e))dp[a][b][c][d][e] += dp[a][b][c-1][d][e];if(check(a, b, c, d-1, e))dp[a][b][c][d][e] += dp[a][b][c][d-1][e];if(check(a, b, c, d, e-1))dp[a][b][c][d][e] += dp[a][b][c][d][e-1];}}}}}//cout << "ans = ";cout << dp[n[1]][n[2]][n[3]][n[4]][n[5]] << endl;
}
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);while(1){cin >> k;if(k == 0)break;memset(n, 0, sizeof(n));for(int i = 1; i <= k; i++)cin >> n[i];solve();}return 0;
}

最长公共上升子序列

题意：

给定两个序列 $a,b$，询问最长公共上升子序列的长度

解析：

令 $f_{i,j}$ 为在 $a$ 的前 $i$ 个数和 $b$ 的前 $j$ 个数中以 $b_j$ 的最长公共上升子序列的长度。

• 不选 $a_i$，$f_{i,j}=f_{i-1,j}$
• 选了 $a_i$，fi,j=max⁡bk<bj{fi−1,k+1}f_{i,j} = \max\limits_{b_k<b_j}\{f_{i-1,k}+1\}fi,j​=bk​<bj​max​{fi−1,k​+1}

此时时间复杂度为 $O(n^3)$。

容易发现每次都是从 $a_i>b_k$ 的前缀最大值转移过来，增加一个变量记录 $f_{i-1,k}$ 的前缀最大值。此时时间复杂度为 $O(n^2)$

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 3e3+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;int n, a[maxn], b[maxn];
int f[maxn][maxn], ans;
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n;for(int i = 1; i <= n; i++)cin >> a[i];for(int i = 1; i <= n; i++)cin >> b[i];for(int i = 1; i <= n; i++){int maxx = 0;for(int j = 1; j <= n; j++){f[i][j] = f[i-1][j];if(a[i] == b[j])f[i][j] = max(f[i][j], maxx+1);else if(a[i] > b[j])maxx = max(maxx, f[i][j]);if(i == n)ans = max(ans, f[i][j]);}}cout << ans << endl;return 0;
}

分级

题意：

给定序列 $A$，构造非严格的单调序列 $B$，使 $S=\sum _{i=1}^n|A_i-B_i|$ 最小。询问最小值。

解析

结论： 一定存在一组最优解，使得每个 $B_i$ 都存在 $j$，满足 $B_i=A_j$

令 $f_{i,j}$ 为确定前 $i$ 数，且第 $i$ 个数为 $C_j$ ，$C$ 为升序排序后的 $A$ 序列。
fi,j=min⁡k<=j{fi−1,k+∣Cj−Ai∣}f_{i,j} = \min\limits_{k <= j}\{ f_{i-1,k} + |C_j-A_i|\}fi,j​=k<=jmin​{fi−1,k​+∣Cj​−Ai​∣}维护前缀最小值，可在 $O(1)$ 时间转移

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 2e3+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;int n, a[maxn], c[maxn];
int ans = INF;
bool cmp(int a, int b){return a > b;
}
int f[maxn][maxn];
void solve(){memset(f, 0, sizeof(f));int res = INF;	for(int i = 1; i <= n; i++){int minn = INF;for(int j = 1; j <= n; j++){minn = min(minn, f[i-1][j]);f[i][j] = minn + abs(a[i]-c[j]);}}for(int i = 1; i <= n; i++)res = min(res, f[n][i]);ans = min(ans, res);
}
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n;for(int i = 1; i <= n; i++){cin >> a[i];c[i] = a[i];}sort(c+1, c+1+n);solve();sort(c+1, c+1+n, cmp);solve();cout << ans << endl;return 0;
}

移动服务

题意：

有 3 个人。有 $n$ 个请求一个人去某地，移动有代价。依次满足请求，询问最小代价。

题意：

令 $f_{i,x,y}$ 表示满足前 $i$ 个请求后，三人位于 $po{s}_i,x,y$ 时的最小代价。

每个状态可以转移到另外三个状态，见代码。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e3+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;int L, n;
int p[maxn], c[210][210];
int dp[maxn][210][210];
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> L >> n;	for(int i = 1; i <= L; i++)for(int j = 1; j <= L; j++)cin >> c[i][j];for(int i = 1; i <= n; i++)cin >> p[i];memset(dp, INF, sizeof(dp));dp[0][1][2] = 0; p[0] = 3;for(int i = 0; i < n; i++){for(int x = 1; x <= L; x++){for(int y = 1; y <= L; y++){if(x == y || y == p[i] || x == p[i])continue;int u = p[i+1];dp[i+1][x][y] = min(dp[i+1][x][y], dp[i][x][y] + c[p[i]][u]);dp[i+1][x][p[i]] = min(dp[i+1][x][p[i]], dp[i][x][y] + c[y][u]);dp[i+1][p[i]][y] = min(dp[i+1][p[i]][y], dp[i][x][y] + c[x][u]);}}}int res = INF;for(int i = 1; i <= L; i++)for(int j = 1; j <= L; j++)res = min(res, dp[n][i][j]);cout << res << endl;return 0;
}

传纸条

题意：

$m\times n$ 的矩阵，每次可以向右或者向下走一步。从左上角都右下角选择两条互不相交（在路径端点可以相交）的路径，使点权和最大。

解析：

令 $f_{i,j,x,y}$ 为第一条路径走到 $(i,j)$ 且第二条路径走到 $(x,y)$ 的最大点权和

对于 $(i,j)=(x,y)$ 的状态，只计算一次点权

也可以网络流。

把每个点拆成入点和出点，入点向出点连边，容量1，费用为点权。

每个点的出点向能到达的点的入点连边，容量INF，费用 0；再连一条边，容量INF，费用 0.

源点向起点的入点连边，容量2，费用 0；终点的出点向汇点连边，容量2，费用 0 。

参考洛谷上 Duan2baka 大佬题解

代码：

#include<iostream>
#include<algorithm>
using namespace std;
int dp[55][55][55][55],a[55][55],n,m;
int main(){cin >> m >> n;for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++)cin >> a[i][j];}for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)for (int k = 1; k <= m; k++)for (int l = 1; l <= n; l++) {dp[i][j][k][l]=max(max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]),max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]))+a[i][j]+a[k][l];if(i==k && j==l) dp[i][j][k][l] -= a[i][j];}cout << dp[m][n][m][n];
}

饼干

题意：

$m$ 个饼干，分给 $n$ 个人。每个人有参数 $g_i$，如果有 $a_i$ 个人的饼干多于 $i$ ，则 $i$ 产生 $a_i\times g_i$ 的怨气。

每个孩子最少分一个饼干，询问最少的怨气。

解析：

贪心的考虑，$g$ 大的人一定分的多于 $g$ 少的人。否则可以交换，结果不会变劣。

令 $f_{i,j}$ 为前 $i$ 个孩子分了 $j$ 个饼干的最小怨气和。

如果当前第 $i$ 个人的饼干数大于 1，则前 $i$ 个人饼干数都大于 1。每个人都减去一个饼干，$a$ 不变，所以 $f_{i,j}=f_{i,j-i}$ 。

如果当前第 $i$ 个人的饼干数为1，枚举有多少人饼干数不为 1

fi,j=min⁡0≤k<i{fk,j−i+k+k∑t=k+1igt}f_{i,j} = \min\limits_{0\le k<i}\{f_{k,j-i+k}+k\sum\limits_{t = k+1}\limits^ig_t\}fi,j​=0≤k<imin​{fk,j−i+k​+kt=k+1∑i​gt​}

时间复杂度为 $O(n^{3}m)$。也可以前缀和优化一下，时间复杂度变成 $O(n^{2}m)$。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define mkp(a, b) make_pair((a), (b))
const int maxn = 3e2+10;
const int maxm = 5e3+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;struct node{int g, id;node(){}node(int g, int id) : g(g), id(id){}bool operator < (const node &b) const{return g > b.g;}
}s[maxn];
int g[maxn], sum[maxn];
int f[maxn][maxm];
pii fr[maxn][maxm];
int res[maxn];
void cal(int x, int y){if(x == 0)return;cal(fr[x][y].first, fr[x][y].second);if(fr[x][y].first == x){for(int i = 1; i <= x; i++)res[s[i].id]++;}else{for(int i = fr[x][y].first+1; i <= x; i++)res[s[i].id] = 1;}
}
int n, m;
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> m;for(int i = 1; i <= n; i++){cin >> s[i].g;s[i].id = i;}		sort(s+1, s+1+n);for(int i = 1; i <= n; i++)sum[i] = sum[i-1] + s[i].g;memset(f, INF, sizeof(f));f[0][0] = 0;for(int i = 1; i <= n; i++){for(int j = i; j <= m; j++){f[i][j] = f[i][j-i];fr[i][j] = mkp(i, j-i);for(int k = 0; k < i; k++){if(f[i][j] > f[k][j-i+k] + k*(sum[i]-sum[k])){f[i][j] = f[k][j-i+k] + k*(sum[i]-sum[k]);fr[i][j] = mkp(k, j-i+k);}}}}cout << f[n][m] << endl;cal(n, m);for(int i = 1; i <= n; i++)cout << res[i] << " ";cout << endl;return 0;
}