Codeforces 750E 세그먼트 트리 DP
사고방식: 라인 트리에 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]);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.