离散化 #dp #贪心
对左右端点离散化，令 \(L=min(r_i),R=max(L_i)\)
\(dp_i\) 表示将所有碰到 \([L,i]\) 这个区间的连起来的最小代价
可以枚举所有的区间，对于所有的包含 \(i\) 的区间，因为 \(dp\) 单调递增，直接从它的左端点转移
反过来处理 \(f_i\) 表示连接 \([i,R]\) 这个区间的最小代价
对于每一个区间，总代价有 \(2\) 种情况，分别是
- \(dp_{l_i}+f_{r_i}\)
- \(min (dp_{l_j}+f_{r_j}+1)\) 其中 \(l_j\leq l_i\) 且 \(r_i\leq r_j\)
暴力转移，时间复杂度是 \(O(n^2)\)
// Author: xiaruize
#ifndef ONLINE_JUDGE
bool start_of_memory_use;
#endif
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
clock_t start_clock = clock();
#endif
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)
{
if (a > b)
return a;
return b;
}
int min(int a, int b)
{
if (a < b)
return a;
return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 2500 + 10;
int n;
string str;
int s[N], t[N];
pii a[N];
int fa[N];
int l = INF, r;
int dp[N << 1], f[N << 1];
int get(int x)
{
if (x == fa[x])
return x;
return fa[x] = get(fa[x]);
}
void solve()
{
cin >> n;
str = "";
rep(i, 1, n)
{
string tmp;
cin >> tmp;
str += tmp;
}
rep(i, 1, str.size()) s[i] += (str[i - 1] - '0') * 1000;
cin >> n;
str = "";
rep(i, 1, n)
{
string tmp;
cin >> tmp;
str += tmp;
}
rep(i, 1, str.size()) s[i] += (str[i - 1] - '0') * 100;
cin >> n;
str = "";
rep(i, 1, n)
{
string tmp;
cin >> tmp;
str += tmp;
}
rep(i, 1, str.size()) s[i] += (str[i - 1] - '0') * 10;
cin >> n;
str = "";
rep(i, 1, n)
{
string tmp;
cin >> tmp;
str += tmp;
}
rep(i, 1, str.size()) s[i] += (str[i - 1] - '0');
cin >> n;
str = "";
rep(i, 1, n)
{
string tmp;
cin >> tmp;
str += tmp;
}
rep(i, 1, str.size()) t[i] += (str[i - 1] - '0') * 1000;
cin >> n;
str = "";
rep(i, 1, n)
{
string tmp;
cin >> tmp;
str += tmp;
}
rep(i, 1, str.size()) t[i] += (str[i - 1] - '0') * 100;
cin >> n;
str = "";
rep(i, 1, n)
{
string tmp;
cin >> tmp;
str += tmp;
}
rep(i, 1, str.size()) t[i] += (str[i - 1] - '0') * 10;
cin >> n;
str = "";
rep(i, 1, n)
{
string tmp;
cin >> tmp;
str += tmp;
}
rep(i, 1, str.size()) t[i] += (str[i - 1] - '0');
n = str.size();
rep(i, 1, n) fa[i] = i;
vector<int> uni;
rep(i, 1, n)
{
a[i] = {s[i], t[i]};
uni.push_back(s[i]);
uni.push_back(t[i]);
rep(j, 1, n)
{
if (i != j)
{
if (s[i] <= t[j] && t[i] >= s[j])
{
fa[get(i)] = get(j);
// cerr << i << ' ' << j << endl;
}
}
}
}
rep(i, 1, n - 1)
{
if (get(i) != get(i + 1))
{
cout << "-1" << endl;
return;
}
}
sort(ALL(uni));
uni.resize(unique(ALL(uni)) - uni.begin());
int m = uni.size();
rep(i, 1, n)
{
a[i].first = lower_bound(ALL(uni), a[i].first) - uni.begin() + 1;
a[i].second = lower_bound(ALL(uni), a[i].second) - uni.begin() + 1;
// cerr << a[i].first << ' ' << a[i].second << endl;
l = min(l, a[i].second);
r = max(r, a[i].first);
}
mms(dp, 0x3f);
mms(f, 0x3f);
rep(i, 1, l) dp[i] = 0;
per(i, m, r) f[i] = 0;
rep(i, l, m)
{
rep(j, 1, n)
{
if (a[j].first <= i && i <= a[j].second)
dp[i] = min(dp[i], dp[a[j].first] + 1);
}
}
per(i, r, 1)
{
rep(j, 1, n)
{
if (a[j].first <= i && i <= a[j].second)
f[i] = min(f[i], f[a[j].second] + 1);
}
}
int res = 0;
// rep(i, 1, m)
// {
// cerr << dp[i] << ' ' << f[i] << endl;
// }
rep(i, 1, n)
{
int tmp = INF;
rep(j, 1, n)
{
if (a[j].first <= a[i].first && a[i].second <= a[j].second)
tmp = min(tmp, dp[a[j].first] + f[a[j].second] + (i != j));
}
res += tmp;
}
cout << res << endl;
}
#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testcase = 1;
// cin >> testcase;
while (testcase--)
solve();
#ifndef ONLINE_JUDGE
cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
return 0;
}