Fragmentation merging-填坑dp

D. Fragmentation merging

https://codeforces.com/gym/103104/problem/D

题意

给定一个长度为n（\(n<=5e3\)）的排列
每次操作可以选择两个不相交的区间，如果两个区间并起来的新区间是连续的一段数(\(max - mi + 1 = len\)),那这两个区间就可以合并。
问最终有多少个不同的合并区间。

思路

对于一个合并后的区间，设它的元素范围在\([mi, mx]\), 这些元素的下标必须大部分连续，即这些元素最多分成两段连续段，否则这个区间对答案没有贡献。
那么已知\([mi, mx]\)连续段个数, 我们可以很容易得知\([mi, mx + 1]\)连续段的个数。
如果\(mx+1\)两边的数都在\([mi, mx]\)范围内, 那么\([mi, mx + 1]\)的连续段个数就要在此基础上减一。
如果\(mx+1\)一边的数在\([mi, mx]\)范围内， 那么连续段的个数与上个状态相同。
如果两边都不在范围内，那么连续段的个数就要加一。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define int ll

#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 5e3 + 5;
const int M = 2e4 + 5;
const ll mod = 998244353;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;

int n, m, k;
int a[N];
int f[N][N], pos[N];

void solve() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		pos[a[i]] = i;
	}

	if(n == 1) {
		cout << 0 << "\n";
		return;
	}
	
	for(int i = 1; i <= n; i++) {
		f[i][i] = 1;
		for(int j = i + 1; j <= n; j++) {
			if(pos[j] == 1) {
				if(a[pos[j] + 1] < j && a[pos[j] + 1] >= i) 
					f[i][j] = f[i][j - 1];
				else f[i][j] = f[i][j - 1] + 1;
				continue;
			} 

			if(pos[j] == n) {
				if(a[pos[j] - 1] < j && a[pos[j] - 1] >= i)
					f[i][j] = f[i][j - 1];
				else f[i][j] = f[i][j - 1] + 1;
				continue;
			}

			int f1 = 0, f2 = 0;
			if(a[pos[j] - 1] < j && a[pos[j] - 1] >= i) f1 = 1;
			if(a[pos[j] + 1] < j && a[pos[j] + 1] >= i) f2 = 1;
			if(f1 && f2) f[i][j] = f[i][j - 1] - 1;
			else if(f1 || f2) f[i][j] = f[i][j - 1];
			else f[i][j] = f[i][j - 1] + 1;
		}
	}

	int ans = 0;
	for(int i = 1; i <= n; i++) {
		for(int j = i; j <= n; j++) {
			//cerr << f[i][j] << " \n"[j == n];
			if(f[i][j] <= 2) ans++;
		}
	}
	cout << ans << "\n";
}

signed main() {
	IOS;
	int __t = 1;
	cin >> __t;
	while (__t--) {
		solve();
	}
}