动态规划练习¶
2025-04-07
最近准备练点动态规划的题。。。但是其实好像只是在洛谷写了几个绿色的板子题。基本都是很简单的难度。
感觉也是可以稍微记录一下吧，但是后面得稍微写点难点的题了，虽然有的绿也是感觉没啥思路。
稍微总结一下。感觉都还是比较典的题，挺好的，补起来应该也不会很困难。
洛谷P2679 普及+/提高¶
感觉好像没啥好说的，枚举 \(A_i\) 和 \(B_j\) 匹配，匹配了多少段。\(i\) 这一维只需要知道前一位的情况，可以用滚动数组。
\(dp_{i,j,l}\) 表示 \(A_{i}\) 和 \(B_j\) 匹配用了 \(l\) 段的方案数。
转移方程为 \(dp_{i,j,l}=\sum\limits_{k=1}^{i-1}{dp_{k,j-1,l-1}}+dp_{i-1,j-1,l}\) 。
所以我们其实只需要知道前缀的和，以及 \(dp_{i-1}\) ，所以可以使用滚动数组，再用一个数组来记前缀和。
constexpr int mod = 1000000007;
int dp[2][202][202];
void ChatGptDeepSeek()
{
int n, m, k;
cin >> n >> m >> k;
vector<char> A(n + 1), B(m + 1);
for (int i = 1; i <= n; i++)
cin >> A[i];
for (int i = 1; i <= m; i++)
cin >> B[i];
vector<vector<int>> DP(m + 1, vector<int>(k + 1));
dp[0][0][0] = DP[0][0] = 1;
for (int i = 1; i <= n; i++)
{
vector nDP = DP;
for (int j = 1; j <= min(i, m); j++)
{
if (A[i] == B[j])
{
for (int l = 1; l <= min(k, j); l++)
{
dp[i & 1][j][l] = (dp[i & 1][j][l] + DP[j - 1][l - 1]) % mod;
nDP[j][l] = (nDP[j][l] + DP[j - 1][l - 1]) % mod;
dp[i & 1][j][l] = (dp[i & 1][j][l] + dp[(i ^ 1) & 1][j - 1][l]) % mod;
nDP[j][l] = (nDP[j][l] + dp[(i ^ 1) & 1][j - 1][l]) % mod;
}
}
}
for (int j = 0; j <= min(i, m); j++)
for (int l = 1; l <= min(k, j); l++)
dp[(i ^ 1) & 1][j][l] = 0;
DP = nDP;
}
cout << DP[m][k] << '\n';
}
洛谷P1541 普及+/提高¶
这个很基础的题目了，虽然标的有绿，但是实际难度并非很高，应该还是比较容易想出来的。只需要枚举每种类型类型的卡片用了多少次。
因为走的步数是可以根据用的卡片的情况直接算出的。
int dp[41][41][41][41];
void ChatGptDeepSeek()
{
int n, m;
cin >> n >> m;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
vector<int> b(4);
for (int i = 1; i <= m; i++)
{
int x;
cin >> x;
b[x - 1]++;
}
dp[0][0][0][0] = a[1];
for (int i = 0; i <= b[0]; i++)
for (int j = 0; j <= b[1]; j++)
for (int k = 0; k <= b[2]; k++)
for (int l = 0; l <= b[3]; l++)
{
int len = i * 1 + j * 2 + k * 3 + l * 4;
// dp[i][j][k][l] = a[1];
// cerr << len << '\n';
if (i - 1 >= 0)
dp[i][j][k][l] = max(dp[i][j][k][l], dp[i - 1][j][k][l] + a[len + 1]);
if (j - 1 >= 0)
dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j - 1][k][l] + a[len + 1]);
if (k - 1 >= 0)
dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k - 1][l] + a[len + 1]);
if (l - 1 >= 0)
dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k][l - 1] + a[len + 1]);
}
cout << dp[b[0]][b[1]][b[2]][b[3]] << '\n';
}
洛谷P1868 普及+/提高¶
也是比较容易想到的了。定义 \(dp_i\) 为 \([1,i]\) 的最大答案。
那么对于每一个区间 \([l,r]\) ，我们可以更新 \(dp_r=dp_{l-1}+r-l+1\) 。
constexpr int N = 3e6 + 10;
int dp[N];
void ChatGptDeepSeek()
{
int n;
cin >> n;
vector<pair<int, int>> v(n);
for (int i = 0; i < n; i++)
cin >> v[i].first >> v[i].second;
sort(v.begin(), v.end());
int j = 0;
for (int i = 0; i <= 3000000; i++)
{
while (j < v.size() && v[j].first == i)
{
auto [l, r] = v[j];
j++;
dp[r] = max(dp[r], (l ? dp[l - 1] : 0) + r - l + 1);
}
dp[i] = max(dp[i], dp[i - 1]);
}
cout << dp[3000000] << '\n';
}
洛谷P1156 普及+/提高¶
也是比较常规的题目。维护每一个高度时的最大的体力值。
只需要注意下，输入的时间不全是按时间排序的。
void ChatGptDeepSeek()
{
int D, G;
cin >> D >> G;
vector<int> T(G), F(G), H(G);
{
vector<array<int, 3>> tmp(G);
for (int i = 0; i < G; i++)
cin >> tmp[i][0] >> tmp[i][1] >> tmp[i][2];
sort(tmp.begin(), tmp.end());
for (int i = 0; i < G; i++)
T[i] = tmp[i][0], F[i] = tmp[i][1], H[i] = tmp[i][2];
}
// for (int i = 0; i < G; i++)
// cin >> T[i] >> F[i] >> H[i];
dp[1][0] = 10;
// for (int i = 1; i <= 25000; i++)
// dp[1][i] = dp[0][i] = -1;
for (int i = 0; i < G; i++)
{
for (int j = 0; j <= 25000; j++)
{
if (dp[(i & 1) ^ 1][j] >= T[i])
{
if (j + H[i] >= D)
{
// cerr << j << " " << dp[(i & 1) ^ 1][j] << " \n";
cout << T[i] << '\n';
return;
}
if (j + H[i] <= 25000)
dp[(i & 1)][j + H[i]] = max(dp[(i & 1)][j + H[i]], dp[(i & 1) ^ 1][j]);
dp[(i & 1)][j] = max(dp[(i & 1)][j], dp[(i & 1) ^ 1][j] + F[i]);
// cerr << i << " " << j << '\n';
}
}
// for (int j = 1; j <= 25000; j++)
// dp[(i & 1) ^ 1][j] = -1;
}
// 如果不行的话 就一直吃！
int now = 10;
for (int i = 0; i < G; i++)
{
// cerr << now << " " << T[i] << '\n';
if (now < T[i])
break;
now += F[i];
}
cout << now << '\n';
}
洛谷P3558 普及+/提高¶
其实也不是很难，只需要稍微思考一下。虽然说 WA 了几次，刚开始题目没看清。。。然后思路也是有问题的。后来稍微改一下就好了。神奇的是，这五题居然都不用看题解。
枚举每一位变成 \(-1,0,1\) 的前缀的答案，\(a_i\) 最多会被前面的数字加两次，且加了之后一定要大于等于前面的数字。
void ChatGptDeepSeek() // Date: 2025-04-07
{ // Time: 17:51:48
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
// 枚举每一位变成 -1 0 1 的答案
vector<vector<int>> dp(n + 1, vector<int>(3, 1e9));
// ... 好像想复杂了的
dp[1][a[1] + 1] = 0;
for (int i = 2; i <= n; i++)
{
for (int x = -1; x <= 1; x++)
{
for (int z = 0; z <= 2; z++)
{
int y = a[i] + z * x;
if (y < x || y > 1)
continue;
dp[i][y + 1] = min(dp[i][y + 1], dp[i - 1][x + 1] + z);
}
}
}
int ans = min({dp[n][0], dp[n][1], dp[n][2]});
if (ans == 1e9)
cout << "BRAK\n";
else
cout << ans << '\n';
}
洛谷P5322 普及+/提高¶
又一道水题，直接枚举就行吧。复杂度 \(O(nms)\)
枚举派了 \(k\) 个人的最大得分。
int dp[2][20002];
void ChatGptDeepSeek() // Date: 2025-04-07
{ // Time: 19:29:06
int s, n, m;
cin >> s >> n >> m;
vector<vector<int>> a(n + 1, vector<int>(s + 1));
for (int i = 1; i <= s; i++)
{
for (int j = 1; j <= n; j++)
cin >> a[j][i];
}
for (int i = 1; i <= n; i++)
{
sort(a[i].begin() + 1, a[i].end());
for (int j = 1; j <= s; j++)
{
int need = 2 * a[i][j] + 1;
if (need > m)
break;
for (int k = m; k >= need; k--)
{
dp[i & 1][k] = max(dp[i & 1][k], dp[i & 1 ^ 1][k - need] + i * j);
// cerr << dp[k] << " ";
}
// cerr << '\n';
}
for (int k = 0; k <= m; k++)
dp[i & 1 ^ 1][k] = dp[i & 1][k];
// cout << *max_element(dp + 1, dp + m + 1) << '\n';
}
int ans = 0;
for (int i = 0; i <= m; i++)
ans = max(ans, dp[n & 1][i]);
cout << ans << '\n';
}
洛谷P1880 普及+/提高¶
石子合并，应该是区间 DP 这一块的模板题了。也是第一次自己 AC 出的绿色的区间 DP 题。
但是刚开始看到是可能没啥思路。。或者说没怎么想。于是去搜了下区间 DP ，结果看到一个 石子合并[弱化版] ，于是花了半小时 AC 了它，于是再看这题发现只是变成了环形的情况，数据范围还变小了。于是花了 40 分钟 AC 了这题。
其实跟弱化版其实没区别，其实不用怎么特殊处理环形的。就是区间 DP 模板的，如果不太会，可以先学习一下再来 AC 。
ll dp[2][114][114];
void ChatGptDeepSeek() // Date: 2025-04-07
{ // Time: 20:35:26
int n;
cin >> n;
vector<int> a(n + 1), pre(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
}
auto get = [&](int l, int r)
{
if (l <= r)
return pre[r] - pre[l - 1];
else
return pre[n] - pre[l - 1] + pre[r];
};
{ // 先把最小值求了吧
for (int i = 0; i < 114; i++)
for (int j = 0; j < 114; j++)
dp[0][i][j] = 1e9;
for (int i = 1; i <= n; i++)
dp[0][i][i] = 0;
for (int len = 2; len <= n; len++)
{
for (int l = 1; l <= n; l++)
{
int r = l + len - 1;
if (r > n)
r -= n;
for (int k = l; k != r; k++)
{
if (k > n)
{
k = 0;
continue;
}
dp[0][l][r] = min(dp[0][l][r], dp[0][l][k] + dp[0][(k + 1 > n ? k + 1 - n : k + 1)][r] + get(l, r));
dp[1][l][r] = max(dp[1][l][r], dp[1][l][k] + dp[1][(k + 1 > n ? k + 1 - n : k + 1)][r] + get(l, r));
}
}
}
ll ans[]{1000000000, 0};
for (int l = 1; l <= n; l++)
{
int r = l + n - 1;
if (r > n)
r -= n;
ans[0] = min(ans[0], dp[0][l][r]), ans[1] = max(ans[1], dp[1][l][r]);
}
cout << ans[0] << '\n'
<< ans[1] << '\n';
}
}
洛谷P1775 普及/提高-¶
双倍经验了属于是。。虽然这题只是黄难度，但如果之前是没见过区间 DP 的话，应该会比较难想出来。比如我。只在前不久的一个 Div. 3 的 G 题见过区间 DP ，约等于抄的题解，还抄了一个蓝题的题解，调色那个。所以这次我自己想出来了。因为就是模板啊。。。
ll dp[303][303];
void ChatGptDeepSeek() // Date: 2025-04-07
{ // Time: 20:41:23
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 0; i <= 302; i++)
for (int j = 0; j <= 302; j++)
dp[i][j] = 1e9;
for (int i = 1; i <= n; i++)
cin >> a[i], dp[i][i] = 0;
vector<int> pre(n + 1);
for (int i = 1; i <= n; i++)
pre[i] = pre[i - 1] + a[i];
for (int len = 2; len <= n; len++)
{
for (int l = 1; l + len - 1 <= n; l++)
{
int r = l + len - 1;
for (int k = l; k < r; k++)
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + pre[r] - pre[l - 1]);
}
}
cout << dp[1][n] << '\n';
}
洛谷P3146 普及+/提高¶
想笑，怎么五分钟不到AC了，虽然代码确实很短。那就不多说了，也是区间DP板子题。
int dp[250][250];
void ChatGptDeepSeek() // Date: 2025-04-08
{ // Time: 15:04:31
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i], dp[i][i] = a[i];
for (int len = 2; len <= n; len++)
{
for (int l = 1; l + len - 1 <= n; l++)
{
int r = l + len - 1;
for (int k = l; k < r; k++)
{
if (dp[l][k] > 0 && dp[k + 1][r] > 0 && dp[l][k] == dp[k + 1][r])
dp[l][r] = max(dp[l][r], dp[l][k] + 1);
}
}
}
int ans=0;
for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) ans=max(ans,dp[i][j]);
cout<<ans<<'\n';
}
洛谷P1063 普及+/提高¶
这题是比较有难度的，因为我们合并的时候是要看后面一个的后一个是什么。这是这个页面到这里第一次看题解。。
\(dp_{l,r}=max(dp_{l,r},dp_{l,k}+dp_{k,r}+a_la_ka_r)\)
因为它这个也是一个环形的，所以最后的答案会是 \(dp_{i,i+n}\) ，这个还是需要一些理解的...
int dp[202][202];
void ChatGptDeepSeek() // Date: 2025-04-08
{ // Time: 16:03:12
int n;
cin >> n;
vector<int> a(2 * n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i], a[i + n] = a[i];
for (int len = 2; len <= n + 1; len++)
for (int l = 1; l + len - 1 <= 2 * n; l++)
{
int r = l + len - 1;
for (int k = l + 1; k < r; k++)
{
dp[l][r] = max(dp[l][r], dp[l][k] + dp[k][r] + a[l] * a[k] * a[r]);
// cerr << l << " " << r << " " << dp[l][r] << '\n';
}
}
int ans = 0;
for (int i = 1; i <= n; i++)
ans = max(ans, dp[i][i + n]);
cout << ans << '\n';
}
洛谷P1040 普及+/提高¶
也是不难的，但看了一下题解的，这题不该看的。看下先序中序的概念就行的。。
先序遍历就是先遍历根节点，再左右节点;中序遍历就是先遍历左子树，再遍历根节点;后续遍历就是先遍历左右子树，再遍历根节点。所以先中后指的都是遍历根节点的顺序。
这题还是比较基础的，算每个 \([l,r]\) 子树的答案。因为最后要输出先序遍历，所以我们再拿个数组记录答案。
void ChatGptDeepSeek() // Date: 2025-04-11
{ // Time: 10:13:41
int n;
cin >> n;
vector<int> d(n + 1);
vector<vi> dp(n + 1, vi(n + 1, 1));
vector<vi> root(n + 1, vi(n + 1));
for (int i = 1; i <= n; i++)
cin >> d[i], dp[i][i] = d[i], root[i][i] = i;
for (int len = 2; len <= n; len++)
{
for (int l = 1; l + len - 1 <= n; l++)
{
int r = l + len - 1;
for (int k = l; k < r; k++)
{
if (dp[l][r] < dp[l][k - 1] * dp[k + 1][r] + dp[k][k])
{
dp[l][r] = dp[l][k - 1] * dp[k + 1][r] + dp[k][k];
root[l][r] = k;
}
}
}
}
auto Print = [&](auto &&self, int l, int r) -> void
{
if (l > r)
return;
cout << root[l][r] << ' ';
if (l == r)
return;
self(self, l, root[l][r] - 1);
self(self, root[l][r] + 1, r);
};
cout << dp[1][n] << '\n';
Print(Print, 1, n);
}
洛谷P1273 普及+/提高¶
本来想的是 \(dp_{u,i}\) 代表 \(u\) 节点赚了 \(i\) 金币的最大人数，但是复杂度会是 \(n^3\) ，而且也不太好写。
其实有时一种思路想不通，可以稍微想想别的，像这种并非很复杂的 DP，总共也不会有很多可能性的。
于是想到可以代表的是 \(u\) 节点的子树有 \(i\) 人的最小花费，然后 TLE 了几个，加了 break 之后就好了，因为每个子树的大小都是有限的。
这是我的第99道绿题，今天再写一题就。。等会杭电比赛，明天蓝桥省赛。
void ChatGptDeepSeek() // Date: 2025-04-11
{ // Time: 11:04:40
int n, m;
cin >> n >> m;
vector<vector<pii>> adj(n + 1, vector<pii>());
for (int i = 1; i <= n - m; i++)
{
int k;
cin >> k;
for (int j = 1; j <= k; j++)
{
int v, w;
cin >> v >> w;
adj[i].push_back({v, w});
}
}
vector<vi> dp(n + 1, vi(m + 1, -INF));
for (int i = 1; i <= n; i++)
dp[i][0] = 0;
for (int i = n - m + 1; i <= n; i++)
{
int x;
cin >> x;
dp[i][1] = x;
}
vector<vi> ndp(dp);
auto dfs = [&](auto &&self, int u, int pre) -> void
{
// cerr << u << '\n';
ndp[u] = dp[u];
for (auto [v, w] : adj[u])
{
if (v == pre)
continue;
self(self, v, u);
// 知道子结点的cost情况 能怎么样呢？
// 改一下 dp[i,j]表示节点i 有j 的贡献 的最小的cost
for (int i = 0; i <= m; i++)
{
if (dp[u][i] == -INF)
break;
for (int j = 0; j + i <= m; j++)
{
if (dp[v][j] == -INF)
break;
ndp[u][i + j] = max(ndp[u][i + j], dp[u][i] + dp[v][j] - w);
}
}
dp[u] = ndp[u];
}
};
dfs(dfs, 1, 0);
for (int i = m; i >= 0; i--)
{
if (dp[1][i] >= 0)
{
cout << i << '\n';
return;
}
}
}