JZTXT

【刷题日记】其一

发布时间 2023-10-31 10:34:02作者: 史上最速败犬

2023.10.27

1400数据结构专练启动

0：41

https://codeforces.com/problemset/problem/816/B 1400数据结构
数据量小，直接用差分实现区间加法，再用前缀和统计出答案

代码 
#include <bits/stdc++.h>
using namespace std;
#define umap unordered_map
#define cy cout << "YES" << endl
#define cn cout << "NO" << endl
#define ll long long
#define forn(i, l, r) for (int i = l; i <= r; i++)
#define forn_(i, l, r) for (int i = l; i >= r; i--)
#define debug(a) cout << #a << "=" << a << endl;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 5;
ll T;

int n, k, q;
int l, r;
int d[N], s[N];
void solve() {
	cin >> n >> k >> q;
	forn(i, 1, n) {
		cin >> l >> r;
		d[l]++, d[r + 1]--;//差分实现区间+
	}

	forn(i, 1, 2e5) d[i] += d[i - 1];//累加起来
	forn(i, 1, 2e5) {
		s[i] += s[i - 1];//前缀和统计答案
		if (d[i] >= k) s[i]++;
	}

	while (q--) {
		cin >> l >> r;
		cout << s[r] - s[l - 1] << endl;//输出区间之和即为答案
	}
}

int main() {
	T = 1;

	while (T--) {
		solve();
	}

	return 0;
}

10：54

https://codeforces.com/problemset/problem/1519/C 1400 前缀和
先排序然后，学校对于每种答案都有贡献，用前缀和优化统计贡献的过程

代码 
#include <bits/stdc++.h>
using namespace std;
#define umap unordered_map
#define cy cout << "YES" << endl
#define cn cout << "NO" << endl
#define ll long long
#define forn(i, l, r) for (int i = l; i <= r; i++)
#define forn_(i, l, r) for (int i = l; i >= r; i--)
#define debug(a) cout << #a << "=" << a << endl;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 5;
ll T;

int n;
struct node {
	ll u, s;
} a[N];
ll sum[N], cnt;
ll ans[N];

bool cmp1(node a, node b) {
	if (a.u == b.u) return a.s > b.s;
	return a.u < b.u;
}

void solve() {
	cin >> n;
	forn(i, 1, n) cin >> a[i].u;
	forn(i, 1, n) cin >> a[i].s;
	sort(a + 1, a + n + 1, cmp1);
	a[n + 1].u = -1;//在i=n的时候特判i+1
	forn(k, 1, n) ans[k] = 0;

	cnt = 0;
	forn(i, 1, n) {
		cnt++;
		sum[cnt] = sum[cnt - 1] + a[i].s;//前缀和
		if (a[i].u != a[i + 1].u) {
			forn(k, 1, n) {//对于每所学校统计贡献
				if (k > cnt) break;
				ans[k] += sum[cnt / k * k];
			}
			cnt = 0;
		}
	}

	forn(k, 1, n) cout << ans[k] << ' ';
	cout << endl;
}

int main() {
	cin >> T;
	// T=1;

	while (T--) {
		solve();
	}

	return 0;
}

11：19

https://codeforces.com/problemset/problem/650/A 1400 数学+哈希（开了仨map）
由数学知识容易知道只有当x或者y坐标相同时，才满足题目条件
所以用哈希存x和y的次数，两两配对有n(n-1)/2种方法
不过记得去重，用map去重并统计坐标出现次数，我们会重复取m（m-1）/2次，减去即可

代码 
#include <bits/stdc++.h>
using namespace std;
#define umap unordered_map
#define cy cout << "YES" << endl
#define cn cout << "NO" << endl
#define ll long long
#define forn(i, l, r) for (int i = l; i <= r; i++)
#define forn_(i, l, r) for (int i = l; i >= r; i--)
#define debug(a) cout << #a << "=" << a << endl;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 5;
ll T;

ll n;
ll x, y;
ll ans;
umap<ll, int> mpx, mpy;
map<pair<ll, ll>, int> mp;
void solve() {
	cin >> n;
	forn(i, 1, n) {
		cin >> x >> y;
		mpx[x]++, mpy[y]++;
		mp[{x, y}]++;
	}

	for (auto i : mpx) {
		ll res = i.second;
		ans += res * (res - 1) / 2;
	}
	for (auto i : mpy) {
		ll res = i.second;
		ans += res * (res - 1) / 2;
	}
	for (auto i : mp) {
		ll res = i.second;
		ans -= res * (res - 1) / 2;
	}

	cout << ans;
}

int main() {
	T = 1;

	while (T--) {
		solve();
	}

	return 0;
}

11：46

https://codeforces.com/problemset/problem/295/A 1400 数据结构 前缀差分
看了题解才悟了，先把询问差分，实现区间+，这样就知道每种操作有多少次，然后每次操作也是区间+，再差分一次即可，最后别忘了加上初始数组的值

代码 
#include <bits/stdc++.h>
using namespace std;
#define umap unordered_map
#define cy cout << "YES" << endl
#define cn cout << "NO" << endl
#define ll long long
#define forn(i, l, r) for (int i = l; i <= r; i++)
#define forn_(i, l, r) for (int i = l; i >= r; i--)
#define debug(a) cout << #a << "=" << a << endl;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 5;
ll T;

ll n, m, k;
ll a[N];
ll l[N], r[N], w[N];
ll d[N], s[N], x, y;
void solve() {
	cin >> n >> m >> k;
	forn(i, 1, n) cin >> a[i];
	forn(i, 1, m) cin >> l[i] >> r[i] >> w[i];
	forn(i, 1, k) {
		cin >> x >> y;
		d[x]++, d[y + 1]--;//差分统计每种操作的次数
	}

	forn(i, 1, m) d[i] += d[i - 1];
	forn(i, 1, m) {//差分统计答案
		s[l[i]] += w[i] * d[i];
		s[r[i] + 1] -= w[i] * d[i];
	}
	forn(i, 1, n) s[i] += s[i - 1], a[i] += s[i];//累加+初始值就是答案

	forn(i, 1, n) cout << a[i] << ' ';
}

int main() {
	T = 1;

	while (T--) {
		solve();
	}

	return 0;
}

12：25

https://codeforces.com/problemset/problem/1279/C 1400 模拟贪心+哈希
很明显，如果我拿到k，那么前面的肯定能通过排序，使得时间变为1，模拟即可，用哈希表示出现过，不过不能从头到尾遍历（因为这个超时了），用一个lst存最后一次拿的地方，下次从这里开始（因为前面的肯定已经处理过了），然后就A了

代码 
#include <bits/stdc++.h>
using namespace std;
#define umap unordered_map
#define cy cout << "YES" << endl
#define cn cout << "NO" << endl
#define ll long long
#define forn(i, l, r) for (int i = l; i <= r; i++)
#define forn_(i, l, r) for (int i = l; i >= r; i--)
#define debug(a) cout << #a << "=" << a << endl;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 5;
ll T;

int n, m;
int a[N], b[N];
ll ans;
int lst;
void solve() {
	umap<int, int> mp, id;
	umap<int, int> is;
	cin >> n >> m;
	forn(i, 1, n) cin >> a[i], id[a[i]] = i;
	forn(i, 1, m) cin >> b[i];

	lst = 1;
	ans = 0;
	forn(i, 1, m) {
		if (mp[b[i]] && !is[b[i]]) {//通过排序把前面出现过的时间变为1
			ans++;
			is[b[i]] = 1;
		}
		if (mp[b[i]]) continue;
		ans += 2 * (id[b[i]] - 1 - i + 1) + 1;  //注意礼物拿完一个后，长度-1
		forn(j, lst, id[b[i]] - 1) mp[a[j]] = 1;//从lst开始遍历
		lst = id[b[i]] + 1;                     //存储上一次拿的位置
	}

	cout << ans << endl;
}

int main() {
	cin >> T;
	// T=1;

	while (T--) {
		solve();
	}

	return 0;
}

吃饭去了

16：23 起床

17：50

https://codeforces.com/problemset/problem/1679/C 1400 数据结构
卡了半天，才发现没开快读，这题其实很简单，查询的时候判断，是不是都有棋子在一行或者一列，每次操作要么放一颗要么拿走一颗，很容易想到用树状数组维护，开两个维护行和列，注意维护的是是否有棋子，而不是棋子总数

代码 
#include <bits/stdc++.h>
using namespace std;
#define umap unordered_map
#define cy cout << "Yes" << endl
#define cn cout << "No" << endl
#define ll long long
#define forn(i, l, r) for (int i = l; i <= r; i++)
#define forn_(i, l, r) for (int i = l; i >= r; i--)
#define debug(a) cout << #a << "=" << a << endl;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 5;
ll T;

class bit {
public:
	bit(int siz) {
		n = siz;
		forn(i, 1, n) t[i] = 0;
	}
	void add(ll x, ll k) {
		while (x <= n) {
			t[x] += k;
			x += lowbit(x);
		}
	}
	ll sum(ll x) {
		ll s = 0;
		while (x > 0) {
			s += t[x];
			x -= lowbit(x);
		}
		return s;
	}
	ll sum(ll l, ll r) {
		return sum(r) - sum(l - 1);
	}

private:
	ll n;
	ll t[N];
	ll lowbit(ll x) {
		return x & -x;
	}
};

ll n, q;
ll x, y, xx, yy;
ll cntc[N], cntr[N];
void solve() {
	cin >> n >> q;
	bit c(n), r(n);

	while (q--) {
		int op;
		cin >> op;
		cin >> x >> y;
		if (op == 1) {
			if (cntc[x] == 0) c.add(x, 1);
			if (cntr[y] == 0) r.add(y, 1);
			cntc[x]++, cntr[y]++;
		}
		if (op == 2) {
			if (cntc[x] == 1) c.add(x, -1);
			if (cntr[y] == 1) r.add(y, -1);
			cntc[x]--, cntr[y]--;
		}
		if (op == 3) {
			cin >> xx >> yy;
			int ok = 0;
			if (c.sum(x, xx) == xx - x + 1) ok = 1;
			if (r.sum(y, yy) == yy - y + 1) ok = 1;
			if (ok) cy;
			else cn;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	T = 1;

	while (T--) {
		solve();
	}

	return 0;
}
封装了个树状数组 
class bit {
public:
	bit(int siz) {
		n = siz;
		forn(i, 1, n) t[i] = 0;
	}
	void add(ll x, ll k) {
		while (x <= n) {
			t[x] += k;
			x += lowbit(x);
		}
	}
	ll sum(ll x) {
		ll s = 0;
		while (x > 0) {
			s += t[x];
			x -= lowbit(x);
		}
		return s;
	}
	ll sum(ll l, ll r) {
		return sum(r) - sum(l - 1);
	}

private:
	ll n;
	ll t[N];
	ll lowbit(ll x) {
		return x & -x;
	}
};

18：13

https://codeforces.com/contest/1679/problem/B 数据结构 1200
做上道题的时候，题解说B题是线段树，就看了下
image
确实是裸的线段树，不过1200分的题没必要，在推平操作时，记录下退平的数lst，之后再单点修改时，就用lst，并打上标记（防止重复）

代码 
#include <bits/stdc++.h>
using namespace std;
#define umap unordered_map
#define cy cout << "YES" << endl
#define cn cout << "NO" << endl
#define ll long long
#define forn(i, l, r) for (int i = l; i <= r; i++)
#define forn_(i, l, r) for (int i = l; i >= r; i--)
#define debug(a) cout << #a << "=" << a << endl;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 5;
ll T;

int n, q;
ll a[N];
ll s;
void solve() {
	cin >> n >> q;
	forn(i, 1, n) cin >> a[i], s += a[i];

	ll op, x, y;
	ll lst;
	umap<int, int> mp;//快速查询是否平推过
	lst = inf;//注意一定要输出化
	while (q--) {
		cin >> op;
		if (op == 1) {
			cin >> x >> y;
			if (lst != inf && !mp[x]) {
				s += y - lst;
				a[x] = y;
				mp[x] = 1;
			} else {
				s += y - a[x];
				a[x] = y;
			}
		}
		if (op == 2) {
			cin >> x;
			s = x * n;
			lst = x;//记录平推的数
			mp.clear();
		}
		cout << s << endl;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	T = 1;

	while (T--) {
		solve();
	}

	return 0;
}

18：38

https://codeforces.com/problemset/problem/713/A 1400 思维二进制
看了题解，发现好妙，把每一个数处理成01串，再把01串处理成整形，就可以统计这种串的形式的个数了

代码 
#include <bits/stdc++.h>
using namespace std;
#define umap unordered_map
#define cy cout << "YES" << endl
#define cn cout << "NO" << endl
#define ll long long
#define forn(i, l, r) for (int i = l; i <= r; i++)
#define forn_(i, l, r) for (int i = l; i >= r; i--)
#define debug(a) cout << #a << "=" << a << endl;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 5;
ll T;

int get(ll x) {
	vector<int> v;
	ll res = 0;
	while (x > 0) {
		v.push_back(x & 1);
		x /= 10;
	}
	x = 1;
	for (auto i : v) {
		res += i * x;
		x *= 2;
	}
	return res;
}

char op;
int num[1 << 18];
ll x;
void solve() {
	cin >> op >> x;
	x = get(x);//处理成一个代号
	if (op == '+') num[x]++;
	if (op == '-') num[x]--;
	if (op == '?') cout << num[x] << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> T;
	// T=1;

	while (T--) {
		solve();
	}

	return 0;
}

19：19

https://codeforces.com/problemset/problem/1468/C 1400 数据结构
测，重载写错了，一直WA7，白调了这么久
题目有求最值，直接用优先队列，每次op=3三的时候直接输出答案
op=2的时候因为是找出现最早的，出现肯定是从1~n，然后把输出的标记一下，每次找到的就是最早的
注意优先队列的顶部，要把标记过的pop出去

代码 
#include <bits/stdc++.h>
using namespace std;
#define umap unordered_map
#define cy cout << "YES" << endl
#define cn cout << "NO" << endl
#define ll long long
#define forn(i, l, r) for (int i = l; i <= r; i++)
#define forn_(i, l, r) for (int i = l; i >= r; i--)
#define debug(a) cout << #a << "=" << a << endl;
const int inf = 0x3f3f3f3f;
const int N = 5e5 + 5;
ll T;

struct node {
	int id, m;
	friend bool operator<(node a, node b) {
		if (a.m != b.m) return a.m < b.m;
		return a.id > b.id;
	}
};
priority_queue<node> q;

int op, x, cnt;
bool is[N];
int vis = 1;
void solve() {
	cin >> op;
	if (op == 1) cin >> x, q.push({++cnt, x});
	if (op == 2) {
		while (is[vis]) vis++;
		is[vis] = 1;
		cout << vis << ' ';
	}
	if (op == 3) {
		while (is[q.top().id]) q.pop();
		is[q.top().id] = 1;
		cout << q.top().id << ' ';
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> T;
	// T=1;

	while (T--) {
		solve();
	}

	return 0;
}

20：00

以这道题结束今天的数据结构专练，特地挑了道1600分的
https://codeforces.com/problemset/problem/1234/D1 1600 数据结构
题目中有单点修改，区间查询，直接上树状数组，对于每一种字符（常数k=26）分别维护，建26个，查询时，如果区间内字符>0，说明存在一种，ans++

代码 
#include <bits/stdc++.h>
using namespace std;
#define umap unordered_map
#define cy cout << "YES" << endl
#define cn cout << "NO" << endl
#define ll long long
#define forn(i, l, r) for (int i = l; i <= r; i++)
#define forn_(i, l, r) for (int i = l; i >= r; i--)
#define debug(a) cout << #a << "=" << a << endl;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 5;
ll T;
class bit {
public:
	bit(){};
	bit(int siz) {
		n = siz;
		forn(i, 1, n) t[i] = 0;
	}
	void add(ll x, ll k) {
		while (x <= n) {
			t[x] += k;
			x += lowbit(x);
		}
	}
	ll sum(ll x) {
		ll s = 0;
		while (x > 0) {
			s += t[x];
			x -= lowbit(x);
		}
		return s;
	}
	ll sum(ll l, ll r) {
		return sum(r) - sum(l - 1);
	}

private:
	ll n;
	ll t[N];
	ll lowbit(ll x) {
		return x & -x;
	}
} t[26];

int n;
string s;
int op, l, r;
char x;
void solve() {
	cin >> op;
	if (op == 1) {
		cin >> l >> x;
		x -= 'a';
		t[s[l]].add(l, -1);
		t[x].add(l, 1);
		s[l] = x;//注意替换
	}
	if (op == 2) {
		cin >> l >> r;
		ll ans = 0;
		forn(i, 0, 25) {
			ll res = t[i].sum(l, r);
			if (res > 0) ans++;
		}
		cout << ans << endl;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	//构造树状数组
	cin >> s;
	n = s.size();
	s = ' ' + s;
	forn(i, 0, 25) t[i] = bit(n);
	forn(i, 1, n) s[i] -= 'a', t[s[i]].add(i, 1);

	cin >> T;
	// T=1;

	while (T--) {
		solve();
	}

	return 0;
}

数据结构1400结束 总结 （0/10）

20：58

吃完饭无聊刷了道题
https://codeforces.com/problemset/problem/1130/C 1400 搜索
数据很小，直接把统计出连通块中的点两两枚举，求最小值

代码 
#include <bits/stdc++.h>
using namespace std;
#define umap unordered_map
#define cy cout << "YES" << endl
#define cn cout << "NO" << endl
#define ll long long
#define forn(i, l, r) for (int i = l; i <= r; i++)
#define forn_(i, l, r) for (int i = l; i >= r; i--)
#define debug(a) cout << #a << "=" << a << endl;
const int inf = 0x3f3f3f3f;
const int N = 1e2 + 5;
ll T;

int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
int n;
struct node {
	int x, y;
};
int sx, sy, fx, fy;
vector<node> s, f;
bool is[N][N];
char g[N][N];
void bfs(int x, int y, vector<node> &v) {
	queue<node> q;
	q.push({x, y});
	v.push_back({x, y});
	is[x][y] = 1;

	while (!q.empty()) {
		node now = q.front();
		q.pop();
		forn(i, 0, 3) {
			int tx = dx[i] + now.x;
			int ty = dy[i] + now.y;
			if (tx < 1 || tx > n || ty < 1 || ty > n) continue;
			if (is[tx][ty]) continue;
			if (g[tx][ty] == '1') continue;
			q.push({tx, ty});
			v.push_back({tx, ty});
			is[tx][ty] = 1;
		}
	}
}
int ans = inf;
void solve() {
	cin >> n;
	cin >> sx >> sy >> fx >> fy;
	forn(i, 1, n) forn(j, 1, n) cin >> g[i][j];

	bfs(sx, sy, s);
	bfs(fx, fy, f);
	for (auto i : s)
		for (auto j : f)
			ans = min(ans, (int) pow(i.x - j.x, 2) + (int) pow(i.y - j.y, 2));
	cout << ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	T = 1;

	while (T--) {
		solve();
	}

	return 0;
}

2023.10.28

玩了半天的邪恶冥刻

17：31 1400 线性DP 找最值

https://codeforces.com/problemset/problem/1350/B
自己原本想出来了转移方程，但是循环写错了，直接贴张图
image

代码 
#include <bits/stdc++.h>
using namespace std;
#define umap unordered_map
#define cy cout << "YES" << endl
#define cn cout << "NO" << endl
#define ll long long
#define forn(i, l, r) for (int i = l; i <= r; i++)
#define forn_(i, l, r) for (int i = l; i >= r; i--)
#define debug(a) cout << #a << "=" << a << endl;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 5;
ll T;

ll n;
ll s[N];
ll f[N];
void solve() {
	cin >> n;
	forn(i, 1, n) cin >> s[i];

	ll ans = 0;
	forn(i, 1, n) f[i] = 1;
	for (ll i = 1; i <= n; i++) {
		for (ll j = 2 * i; j <= n; j += i) {
			if (s[j] > s[i]) f[j] = max(f[j], f[i] + 1);
		}
		ans = max(ans, f[i]);
	}

	cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> T;
	// T=1;

	while (T--) {
		solve();
	}

	return 0;
}

18：15 1400 线性DP 计数

https://codeforces.com/problemset/problem/414/B
跟上一道差不多的转移方式，不过边界条件错了，WA了一次，然后忘记取模了，又WA了一次
f[i][j]表示长度为i，最后一位为j的方案数，转移方程f[i][k] += f[i - 1][j]，ans是长度为len的累加

代码 
#include <bits/stdc++.h>
using namespace std;
#define umap unordered_map
#define cy cout << "YES" << endl
#define cn cout << "NO" << endl
#define ll long long
#define forn(i, l, r) for (int i = l; i <= r; i++)
#define forn_(i, l, r) for (int i = l; i >= r; i--)
#define debug(a) cout << #a << "=" << a << endl;
const int inf = 0x3f3f3f3f;
const int N = 2e3 + 5;
ll T;

ll mod = 1e9 + 7;
ll n, len;
ll ans;
ll f[N][N];
void solve() {
	cin >> n >> len;

	forn(i, 1, n) f[1][i] = 1;
	forn(i, 1, len) {
		forn(j, 1, n) {
			for (int k = j; k <= n; k += j) {
				f[i][k] += f[i - 1][j];
				f[i][k] %= mod;
			}
		}
	}

	forn(i, 1, n) ans += f[len][i], ans %= mod;
	cout << ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//cin >> T;
	T = 1;

	while (T--) {
		solve();
	}

	return 0;
}

大概18：30 1400 线性DP 求最值（暴力也能做）

我一开始用的暴力

暴力 
#include <bits/stdc++.h>
using namespace std;
#define umap unordered_map
#define cy cout << "YES" << endl
#define cn cout << "NO" << endl
#define ll long long
#define forn(i, l, r) for (int i = l; i <= r; i++)
#define forn_(i, l, r) for (int i = l; i >= r; i--)
#define debug(a) cout << #a << "=" << a << endl;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 5;
ll T;

ll n;
ll s[N], c[N];
ll f[N];
ll ans;
void solve() {
	cin >> n;
	forn(i, 1, n) cin >> s[i];
	forn(i, 1, n) cin >> c[i];

	ans = inf;
	memset(f, inf, sizeof f);
	ll res, l, r;
	c[0] = inf;
	forn(i, 1, n) {
		l = r = 0;
		res = inf;
		forn(j, 1, i - 1) {
			if (s[i] > s[j] && c[j] < res) res = c[j], l = j;
		}
		res = inf;
		forn(j, i + 1, n) {
			if (s[j] > s[i] && c[j] < res) res = c[j], r = j;
		}
		ans = min(ans, c[l] + c[i] + c[r]);
	}

	if (ans >= inf) ans = -1;
	cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	T = 1;

	while (T--) {
		solve();
	}

	return 0;
}
后面看题解用的DP
代码 
#include <bits/stdc++.h>
using namespace std;
#define umap unordered_map
#define cy cout << "YES" << endl
#define cn cout << "NO" << endl
#define ll long long
#define forn(i, l, r) for (int i = l; i <= r; i++)
#define forn_(i, l, r) for (int i = l; i >= r; i--)
#define debug(a) cout << #a << "=" << a << endl;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 5;
ll T;

ll n;
ll s[N], c[N];
ll f[N][5];
ll ans;
void solve() {
	cin >> n;
	forn(i, 1, n) cin >> s[i];
	forn(i, 1, n) cin >> c[i];

	memset(f, inf, sizeof f);
	forn(i, 1, n) f[i][1] = c[i];
	forn(i, 1, n) {
		forn(j, 1, i - 1) {
			forn(k, 2, 3) {
				if (s[j] >= s[i]) continue;
				f[i][k] = min(f[i][k], f[j][k - 1] + c[i]);
			}
		}
	}

	ans = inf;
	forn(i, 1, n) ans = min(ans, f[i][3]);
	if (ans >= inf) ans = -1;
	cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	T = 1;

	while (T--) {
		solve();
	}

	return 0;
}

2023.10.29

下面的记得补代码

16：23 1500 线性DP 求最值 决策优化

https://codeforces.com/problemset/problem/1842/C
一开始n方，直接炸了
看题解才会

16：48 1500 线性DP 求最值 决策优化

https://codeforces.com/problemset/problem/1005/D

https://codeforces.com/problemset/problem/1207/C