水题笔记 [Oibh]新型计算机 [DP, 线段树, DP优化]

原来\(0\)是自然数啊...= =+

懵逼的题目

BZOJ

扯淡的题解

设\(f_i\)为以\(i\)为开头到终点最小的代价

为了计算代价, 需要在线段树中把值赋为\(f_i + i\)或者\(f_i + n - i + 1\)

然后分别在i + a[i] + 1的左边和右边找最小值再加加减减一下就行了...

然后\(\mathrm O(n\lg n)\)被卡了...远古神仙WJMZBMR说有\(\mathrm O(n)\)做法...然而不会...也没找到...

沙茶的代码

一开始以为\(0\)不是自然数RE了好久...

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN (1000000 + 5)
#define INF (2000000000)
#define lowbit(x) ((x) & (-(x)))
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define rint register int
#define cint const int 
using namespace std;
struct node {
	int le, ri, zh;
}b1[MAXN << 2], b2[MAXN << 2];
int n, a[MAXN], f[MAXN];
inline int max(cint x, cint y) { return (x > y) ? x : y; }
inline int min(cint x, cint y) { return (x < y) ? x : y; }
void js(node* b, cint dq, cint le, cint ri) {
	b[dq].le = le, b[dq].ri = ri;
	b[dq].zh = INF;
	if (le == ri)	return ;
	cint mi = (le + ri) >> 1;
	js(b, LS(dq), le, mi);
	js(b, RS(dq), mi + 1, ri);
}
void xg(node* b, cint dq, cint wz, cint zh) {
	if (b[dq].le == b[dq].ri) {
		b[dq].zh = min(zh, b[dq].zh);
		return ;
	}
	cint mi = (b[dq].le + b[dq].ri) >> 1;
	if (wz <= mi)	xg(b, LS(dq), wz, zh);
	else	xg(b, RS(dq), wz, zh);
	b[dq].zh = min(b[LS(dq)].zh, b[RS(dq)].zh);
}
int cx(node* b, cint dq, cint le, cint ri) {
	if (b[dq].le == le && b[dq].ri == ri)
		return b[dq].zh;
	cint mi = (b[dq].le + b[dq].ri) >> 1;
	if (ri <= mi)	return cx(b, LS(dq), le, ri);
	else if (le > mi)	return cx(b, RS(dq), le, ri);
	else	return min(cx(b, LS(dq), le, mi), cx(b, RS(dq), mi + 1, ri));
}
void solve() {
	++n;
	js(b1, 1, 1, n), js(b2, 1, 1, n);
	xg(b1, 1, n, n), xg(b2, 1, n, 1);
	for (rint i = n - 1; i >= 1; i--) {
	//	printf("%d %d\n", i, a[i]);
		if (i + a[i] + 1 <= n)	f[i] = min(cx(b1, 1, i + a[i] + 1, n) - i - a[i] - 1, cx(b2, 1, i + 1, i + a[i] + 1) + i + a[i] - n);//, printf("ok %d\n", i);
		else	f[i] = cx(b2, 1, i + 1, n) + i + a[i] - n;//, printf("ok %d\n", i);
		xg(b1, 1, i, f[i] + i);
//		printf("ok %d\n", i);
		xg(b2, 1, i, f[i] + n - i + 1);
//		printf("ok %d\n", i);
	}
}
inline int read() {
	int re = 0;
	char x = 0;
	while (x > '9' || x < '0')	x = getchar();
	while (x <= '9' && x >= '0')	re = (re << 1) + (re << 3) + x - '0', x = getchar();
	return re;
}
int main() {
	freopen("data.in", "r", stdin);
	n = read();
	for (rint i = 1; i <= n; i++)	a[i] = read();
	solve();
	printf("%d", f[1]);
	return 0;
}

懵逼的 题目

扯淡的 题解

沙茶的 代码

懵逼的题目

扯淡的题解

沙茶的代码