【ATC】Make Pair 区间DP

本文主要是介绍【ATC】Make Pair 区间DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送⻔

分析

数据范围不大，所以考虑区间$DP$
令$f[i][j]$表示$i-j$区间内的方案数，设中间点$k$，若$i$和$k$可以匹配，则
$f[i][j]=(f[i][j]+f[i+1][k-1]\ast f[k+1][j]\ast c[l/2][(j-k)/2])$

代码

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
#define _CRT_SECURE_NO_WARNINGS
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int N = 500;
const ll mod = 998244353;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a) {char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {if (c == '-')f = -1; c = getchar();}while (isdigit(c)) {x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}
int gcd(int a, int b) {return (b > 0) ? gcd(b, a % b) : a;}
ll f[N][N],c[N][N];
int n,m;
bool st[N][N];void init() {for (int i = 0; i < N; ++i)for (int j = 0; j <= i; ++j)if (!j)c[i][j] = 1;else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}int main() {init();read(n),read(m);while(m--){int x,y;read(x),read(y);st[x][y] = st[y][x] = 1;}for(int i = 0;i <= 400;i++) f[i + 1][i] = 1;for(int l = 2;l <= n * 2;l += 2){for(int i = 1;i + l - 1 <= 2 * n;i++){int j = i + l - 1;for(int k = i + 1;k <= j;k += 2){if(st[i][k]){f[i][j] = (f[i][j] + f[i + 1][k - 1] * f[k + 1][j] % mod * c[l / 2][(j - k) / 2] % mod) % mod;}}}}dl(f[1][2 * n]);return 0;
}

这篇关于【ATC】Make Pair 区间DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---