dp好题，陆续更新中AtCoder中的一些dp好题

83 阅读 0 评论 55 点赞

我是靠谱客的博主洁净鞋子，最近开发中收集的这篇文章主要介绍dp好题，陆续更新中AtCoder中的一些dp好题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

AtCoder中的一些dp好题

1. AtCoder Beginner Contest 210 D - National Railway

题意：

	有一个n*m的阵列，每个点有一个值a[i][j], 我们需要在这个阵列中找到两个不同的点，连接他们的花费为
a[x1][y1] + a[x2][y2] + （|x1 - x2| + |y1 - y2|) * c,
要求最小的花费是多少？(n <= 1000, m <= 1000)

思路：

	暴力的想法就是把任意两个点拿出来匹配，但是显然是会超时的，这题可以对每一个点进行bfs, 每次向
四周扩展，然后貌似没有优化方法，此时我们应该想到dp, dp可以减少我们的重复计算。
我们考虑dp[i][j]为在左上角（1，1）和（i，j)所围成的阵列中找到一个点，并且从那个点移动到当前点的最小花费
那么dp[i][j]就会有以下3种情况
1.选取点（i, j)
2.从dp[i - 1][j]转移到当前点
3.从dp[i][j - 1]转移到当前点
dp[i][j] = min({dp[i - 1][j] + c, dp[i][j - 1] + c, a[i][j]});
那么我们来考虑我们怎么得到答案，要求两个选取的点是不能够相同的
我们定义是s[i][j]为在（1，1）和（i，j)所围成的阵列中选取点（i，j)为另外一个点所花费总的最小值；
那么是s[i][j] = min(dp[i - 1][j] + c, dp[i][j - 1] + c);
那么我们最后的ans就是是s[i][j]数组中的最小值
然后我惊奇的wa了3个点
经过我的对拍，我发现假如我们当前选取了一个点，我们目前只算出了该点和其右边和下边的点匹配的最小值，
没有考虑该点和他的左边以及上面匹配的最小值
所以我们需要从左上角和右上角做2次dp，然后取min

时间复杂度: O(n * m)

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(X) ((int)(X).size())
#define fi first
#define se second
#define pb push_back
#define rep(i, a, n) for (int i = a; i <= n; i ++ ) 
#define per(i, a, n) for (int i = n; i >= a; i -- )
#define mst memset
#define endl 'n'
#define si(x) scanf("%d", &x)
#define sll(x) scanf("%lld", &x)
#define pi(x) printf("%dn", x)
#define pll(x) printf("%lldn", x)
#define sc scanf
#define pr printf
#define IO ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
using big = long long;
using i64 = unsigned long long;
const int SIZE = 2e5 + 10, INF = 0x3f3f3f3f3f3f3f3f;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
big gcd(big a, big b) { return b ? gcd(b, a % b) : a; }
big ksm(int a, int b, int c) { int ans = 1 % c; while (b) { if (b & 1) { ans = 1ll * ans * a % c; } a = 1ll * a * a % c;
b >>= 1; } return ans;}
constexpr int N = 1010;
int n, m, c, dp[N][N], s[N][N], a[N][N];
void solve() {
cin >> n >> m >> c;
rep(i, 1, n) {
rep(j, 1, m) { cin >> a[i][j]; }
}
memset(dp, 0x3f, sizeof dp);
rep(i, 1, n) {
rep(j, 1, m) {
dp[i][j] = min({a[i][j], dp[i - 1][j] + c, dp[i][j - 1] + c});
}
}
int ans = INF;
rep(i, 1, n) {
rep(j, 1, m) {
ans = min({ans, dp[i - 1][j] + c + a[i][j], dp[i][j - 1] + c + a[i][j]});
}
}
cout << ans << 'n';
}
signed main(void) {
int t;
// cin >> t; 
//	in(t);
t = 1;
while (t -- ) {
solve();
}
return 0;
}

2.AtCoder Beginner Contest 210 E - Chain Contestant

题意：

	给我们一个由10种字符组成的字符串，我们需要从中选取一个子序列（不连续），要求就是子序列同
一种字符必须连续，问我们由多少种选择方式？

思路：

	既然是计数，所以很容易想到他是一个dp?但是是什么dp呢，其实看数据范围很容易看出来是一个状态压缩dp,
我们来看状态表示来解释为什么是一个状态压缩dp, 在遍历到字符串的第I个字符时，考虑该字符选还是不选，
能够选择他的前提是：
1.该字符未在当前子序列中出现；
2.该字符在当前子序列中出现，且该子序列是以该字符为结尾；
那么如果我们仅以f[i]表示前i个字符能选出多少个子序列，状态明显是不够的，我们不知道第i个字符能不能选
那么我们就需要在状态中假如该子序列是啥，显然加不了该子序列是啥，那么我们可以发现我们并不关心该子
序列是啥，我们只需要知道该子序列中出现了哪些字符，结尾字符是什么，那么只有10个字符，显然不可能去开
一个10多维的数组，我们可以想到用一个二进制数去表示哪些字符出现没有
进而状态表示而f[i][state][c]表示考虑前i个字符，字符出现情况为state,以字符c为结尾的子序列个数
f[i][state][c] = f[i - 1][state ^ (1 << c)][(state ^ (1 << c)中出现的字符] + f[i - 1][state][c]
+ f[i - 1][state][c](及不考虑第i个字符）
那么当然就是对f[n][state][c]求和（注意空串不算，所以忽略state为0的情况）
容易忽略的细节就是在每个i的位置，我们可以新建一个子序列，f[i][1 << c][c] = 1;

代码：

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1025, P = 998244353;
string str;
int n;
// assume -P <= x < 2P
int norm(int x) {
if (x < 0) {
x += P;
}
if (x >= P) {
x -= P;
}
return x;
}
template<class T>
T power(T a, int b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
struct Z {
int x;
Z(int x = 0) : x(norm(x)) {}
int val() const {
return x;
}
Z operator-() const {
return Z(norm(P - x));
}
Z inv() const {
assert(x != 0);
return power(*this, P - 2);
}
Z &operator*=(const Z &rhs) {
x = (long long)(x) * rhs.x % P;
return *this;
}
Z &operator+=(const Z &rhs) {
x = norm(x + rhs.x);
return *this;
}
Z &operator-=(const Z &rhs) {
x = norm(x - rhs.x);
return *this;
}
Z &operator/=(const Z &rhs) {
return *this *= rhs.inv();
}
friend Z operator*(const Z &lhs, const Z &rhs) {
Z res = lhs;
res *= rhs;
return res;
}
friend Z operator+(const Z &lhs, const Z &rhs) {
Z res = lhs;
res += rhs;
return res;
}
friend Z operator-(const Z &lhs, const Z &rhs) {
Z res = lhs;
res -= rhs;
return res;
}
friend Z operator/(const Z &lhs, const Z &rhs) {
Z res = lhs;
res /= rhs;
return res;
}
};
Z f[N][N][10];
signed main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> str;
for (int i = 1; i <= str.size(); i ++ )
{
for (int j = 0; j < (1 << 10); j ++ ) {
for (int k = 0; k < 10; k ++ ) {
f[i][j][k] = f[i - 1][j][k];
}
}
int x = str[i - 1] - 'A';
for (int j = 0; j < (1 << 10); j ++ ) {
if ((j >> x) & 1) {
f[i][j][x] += f[i - 1][j][x];
for (int k = 0; k < 10; k ++ ) {
if (k != x) {
f[i][j][x] += f[i - 1][j ^ (1 << x)][k];
}
}
}
}
f[i][1 << x][x] += 1;
}
Z ans;
for (int i = 0; i < (1 << 10); i ++ ) {
for (int j = 0; j < 10; j ++ ) {
ans += f[n][i][j];
}
}
cout << ans.val() << 'n';
return 0;
}