Codeforces 750E 세그먼트 트리 DP

3626 단어
제목: 문자열을 드리겠습니다. 두 가지 동작이 있습니다. 1: 어떤 위치의 문자를 바꿉니다.2: l에서 r까지의 문자열은 최소한 몇 개의 문자를 삭제해야 하는지 묻는다. 이 문자열은 2017 서열을 포함하고 2016 서열이 없도록 합니까?
사고방식: 라인 트리에 DP를 설치하고 우리는 상태 0, 1, 2, 3, 4를 설정한다. 각각:null, 2, 20, 2017, 2017의 최소 비용이다. 우리는 라인 트리로 상호 상태 이동의 비용 행렬을 유지하고 서로 인접한 두 개의 서브열을 합칠 때 직접 이동하면 된다.
코드:
#include 
#define INF 0x3f3f3f3f
#define ls (o << 1)
#define rs (o << 1 | 1)
using namespace std;
const int maxn = 200010;
int a[maxn];
char s[maxn];
struct node {
	int f[5][5];
	void init(int x) {
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 5; j++) {
				if(i == j) continue;
				f[i][j] = INF;
			}
		}
		if(x == 2) {
			f[0][0] = 1, f[0][1] = 0;
		} else if (x == 0) {
			f[1][1] = 1, f[1][2] = 0;			
		} else if (x == 1) {
			f[2][2] = 1, f[2][3] = 0;
		} else if (x == 7) {
			f[3][3] = 1, f[3][4] = 0;
		} else if (x == 6) {
			f[3][3] = 1;
			f[4][4] = 1;
		} else if (x == -1){
			for (int i = 0; i < 5; i++)
				f[i][i] = INF;
		} else {
			for (int i = 0; i < 5; i++)
				f[i][i] = 0;
		}
	}
	
	void print() {
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 5; j++) {
				if(f[i][j] == INF) printf("inf ");
				else printf("%d ", f[i][j]);
			}
			printf("
"); } } }; node tr[maxn * 4]; node merge(node t1, node t2) { node ans; ans.init(-1); // ans.init(-1); // printf("ans
"); // ans.print(); // printf("t1
"); // t1.print(); // printf("t2
"); // t2.print(); for (int i = 0; i < 5; i++) { for (int j = i; j < 5; j++) { for (int k = i; k <= j; k++) { ans.f[i][j] = min(ans.f[i][j], t1.f[i][k] + t2.f[k][j]); } } } // printf("ans
"); // ans.print(); return ans; } void build(int o, int l, int r) { if(l == r) { tr[o].init(a[l]); return; } int mid = (l + r) >> 1; build(ls, l, mid); build(rs, mid + 1, r); tr[o] = merge(tr[ls], tr[rs]); } void update(int o, int l, int r, int ql, int qr, int val) { if(l == r) { tr[o].init(val); return; } int mid = (l + r) >> 1; if(ql <= mid) update(ls, l, mid, ql, qr, val); if(qr > mid) update(rs, mid + 1, r, ql, qr, val); tr[o] = merge(tr[ls], tr[rs]); } node query(int o, int l, int r, int ql, int qr) { if(l >= ql && r <= qr) { return tr[o]; } int mid = (l + r) >> 1; node ans; ans.init(-1); if(ql <= mid && qr > mid) ans = merge(query(ls, l, mid, ql, qr), query(rs, mid + 1, r, ql, qr)); else if(ql <= mid) ans = query(ls, l, mid, ql, qr); else if(qr > mid) ans = query(rs, mid + 1, r, ql, qr); return ans; } int main() { int n, m, l, r; scanf("%d%d", &n, &m); scanf("%s", s + 1); for (int i = 1; i <= n; i++) { a[i] = s[i] - '0'; } build(1, 1, n); for (int i = 1; i <= m; i++) { scanf("%d%d", &l, &r); node ans = query(1, 1, n, l, r); if(ans.f[0][4] == INF) printf("-1
"); else printf("%d
", ans.f[0][4]); } }

좋은 웹페이지 즐겨찾기