POJ 3666 Making the Grade (dp, 데이터 구조 [왼쪽 트 리, 구분 트 리, 함수 식 선분 트 리 등])

11908 단어 데이터 구조dp
제목 유형  dp, 데이터 구조 [왼쪽 트 리, 구분 트 리, 함수 식 선분 트 리 등]
제목
[0, 1e9] 범위 내 에서 최대 2000 개 를 포함 하 는 수열 을 제시 하여 이 수열 을 비 증가 또는 비 체감 수열 로 수정 하 는 최소 대 가 를 물 었 다.
대가 = 원 수열 의 모든 요소 와 수 정 된 수열 의 해당 위치 에 있 는 요소 의 차 이 는 절대적 인 값 과
문제 풀이 방법
1. dp (이산 화)
dp [i] [j]: 앞의 i 개 요 소 는 비 전달 감수 열 을 구성 하고 i 번 째 요소 의 값 은 j 의 최소 대 가 를 계산 하 는 것 처럼 보이 지만 O (n ^ 3) 사실 O (n ^ 2) 를 계산 하면 됩 니 다.
            dp [i] [j] 를 계산 할 때 dp [i] [j - 1] 을 직접 계산 할 때 얻 을 수 있 는 (dp [i - 1] [0] - > dp [i - 1] [j - 1] 이 값 중 최소 값) 정보 이기 때문이다.
            비 증가 수열 의 대 가 는 역시 O (n ^ 2) 시간 내 에 계산 할 수 있다.
2. 논문 의 해법 참고 - >  왼쪽 트 리 의 특징 및 응용
    2.1 방법 을 알 게 된 후에 문제 의 중심 은 특정한 변화 수열 의 중위 수 논문 을 찾 는 방법 으로 바 뀌 었 다. 왼쪽 나무 (나무 뿌리 에 최대 치 를 보존 하고 중위 수) 로 수열 의 왼쪽 부분 을 보존 하 는 것 이다.            다른 수열 을 합 치 려 면 그 수열 의 왼쪽 부분 에 형 성 된 왼쪽 트 리 와 현재 왼쪽 트 리 를 합 쳐 야 합 니 다. 합 친 두 수열 의 요소 개수 가 홀수 일 때 합 친 후 뿌리 를 삭제 해 야 합 니 다.          떨 어 뜨리 기 (예 를 들 어 수열 1, 2, 3 과 수열 4, 5, 6 을 합 친 후 4 개가 아 닌 3 개의 요소 만 포 함 된 왼쪽 나 무 를 얻어 야 합 니 다)
    2.2 사실은 특정한 구간 의 k 소 수 를 찾 는 것 이다.
참조 코드 - 궁금 한 점 이 있 으 시 면 아래 에 댓 글 을 남 겨 주시 면 바로 답 해 드 리 겠 습 니 다.
1.dp 
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;
const int maxn = 2000 + 10;
const LL INF = 1LL<<60;
int a[maxn], b[maxn];
LL dp[2][maxn];

int Abs(int x) { return x < 0 ? -x : x; }

int main() {
//	freopen("in", "r", stdin);
	int n;
	while(scanf("%d", &n) != EOF) {
		for( int i=0; i<n; i++ ) { scanf("%d", &a[i]); b[i] = a[i]; }
		sort(b, b + n);
		int nb = unique(b, b + n) - b;
		for( int i=0; i<nb; i++ ) dp[0][i] = Abs(b[i] - a[0]);
		int now = 0;
		for( int i=1; i<n; i++ ) {
			LL nmin = INF;
			for( int j=0; j<nb; j++ ) {
				nmin = min(nmin, dp[now][j]);
				dp[now^1][j] = nmin + Abs(b[j] - a[i]);
			}
			for( int j=0; j<nb; j++ ) dp[now][j] = INF;
			now ^= 1;
		}
		LL ans = INF;
		for( int i=0; i<nb; i++ ) ans = min(ans, dp[now][i]);

		for( int i=0; i<nb; i++ ) dp[0][i] = Abs(b[i] - a[n-1]);
		now = 0;
		for( int i=n-2; i>=0; i-- ) {
			LL nmin = INF;
			for( int j=nb-1; j>=0; j-- ) {
				nmin = min(nmin, dp[now][j]);
				dp[now^1][j] = nmin + Abs(b[j] - a[i]);
			}
			for( int j=0; j<nb; j++ ) dp[now][j] = INF;
			now ^= 1;
		}
		for( int i=0; i<nb; i++ ) ans = min(ans, dp[now][i]);

		printf("%lld
", ans);
	}
	return 0;
}

2.1 왼쪽 나무
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <cstdlib>

using namespace std;

const int maxn = 2000 + 10;
#define B printf("BUG
");

int a[maxn];
int ans[maxn];

class Node {
public :
	int v;
	int h;
	Node * ch[2];
	Node(int v) : v(v) { ch[0] = ch[1] = NULL; h = 0; }
};

class Seg {
public :
	int n;
	Node * rt;
	Seg(Node * rt, int n) : rt(rt), n(n) {}
};

class Leftist {
public : 

	stack<Seg *>S;

	Node * merge(Node * t1, Node * t2) {
		if(t1 == NULL) return t2;
		else if(t2 == NULL) return t1;
		if(t1->v < t2->v) swap(t1, t2);
		if(t1->ch[1] == NULL) {
			t1->ch[1] = t2;
			if(t1->ch[0] == NULL) { swap(t1->ch[0], t1->ch[1]); t1->h = 0; }
			else {
				if(t1->ch[0]->h < t1->ch[1]->h) swap(t1->ch[0], t1->ch[1]);
				t1->h = t1->ch[1]->h + 1;
			}
		}
		else {
			t1->ch[1] = merge(t1->ch[1], t2);
			if(t1->ch[0] == NULL) { swap(t1->ch[0], t1->ch[1]); t1->h = 0; }
			else {
				if(t1->ch[0]->h < t1->ch[1]->h) swap(t1->ch[0], t1->ch[1]);
				t1->h = t1->ch[1]->h + 1;
			}
		}
		return t1;
	}

	void solve(int x) {
		int num = 1;
		Node * t1 = new Node(x);
		while(!S.empty()) {
			Seg * s2 = S.top();
			if(t1->v < s2->rt->v) {
				int flag = false;
				if(num % 2 && s2->n % 2) flag = true;
				t1 = merge(t1, s2->rt);
				num += s2->n;
				if(flag) {
					Node * tmp = t1;
					t1 = merge(t1->ch[0], t1->ch[1]);
					delete tmp;
				}
				S.pop();
				delete s2;
			}
			else break;
		}
		Seg * s2 = new Seg(t1, num);
		S.push(s2);
	}

	void removetree(Node * rt) {
		if(rt->ch[0] == NULL && rt->ch[1] == NULL) {
			delete rt;
			rt = NULL;
			return ;
		}
		if(rt->ch[0]) removetree(rt->ch[0]);
		if(rt->ch[1]) removetree(rt->ch[1]);
		delete rt;
		rt = NULL;
	}

	void remove() {
		while(!S.empty()) {
			removetree(S.top()->rt);
			delete S.top();
			S.pop();
		}
	}
};

int main() {
	freopen("in", "r", stdin);
	int n;
	while(scanf("%d", &n) != EOF) {
		Leftist lt;
		for( int i=0; i<n; i++ ) {
			scanf("%d", &a[i]);
			lt.solve(a[i]);
		}

		int k = 0;
		while(!lt.S.empty()) {
			Seg * f = lt.S.top(); lt.S.pop();
			for( int i=0; i<f->n; i++ ) {
				ans[k++] = f->rt->v;
			}
		}
		int res = 0;
		for( int i=k-1; i>=0; i-- ) res += abs(ans[i] - a[n-i-1]);
		lt.remove();
		Leftist lt2;
		for( int i=0; i<n/2; i++ ) swap(a[i], a[n-i-1]);
		for( int i=0; i<n; i++ ) lt2.solve(a[i]);
		k = 0;
		while(!lt2.S.empty()) {
			Seg * f = lt2.S.top(); lt2.S.pop();
			for( int i=0; i<f->n; i++ ) {
				ans[k++] = f->rt->v;
			}
		}
		int res2 = 0;
		for( int i=k-1; i>=0; i-- ) res2 += abs(ans[i] - a[n-i-1]);
		lt2.remove();
		res = min(res, res2);
		printf("%d
", res);
	}
	return 0;
}

2.2 구분 수
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <cstdlib>
#include <algorithm>

using namespace std;

const int maxn = 2000 + 10;
#define B printf("BUG
");

int a[maxn], b[maxn], A[maxn];
int ans[maxn];
int n, N;

class Seg {
public :
	int l, r;
	int nmid;
	Seg(int l, int r, int nmid) : l(l), r(r), nmid(nmid) {}
};

int tree[20][2010], movel[20][2010];

class DivTree {
public : 

	void build(int rt, int l, int r) {
		if(l == r) { tree[rt][l] = tree[rt-1][l]; return ; }
		int mid = (l+r)>>1;
		int c = 0, d = 0;
		for( int i=l; i<=r; i++ ) {
			int pos = tree[rt-1][i];
			movel[rt][i] = i==l?0:movel[rt][i-1];
			if(A[pos] <= mid) { 
				tree[rt][l+c] = pos;
				c++; movel[rt][i]++; 
			}
			else {
				tree[rt][mid+1+d] = pos;
				d++;
			}
		}
		build(rt+1, l, mid); build(rt+1, mid+1, r);
	}

	int query_mid(int rt, int l, int r, int L, int R, int k) {
		int mid = (l+r)>>1;
		if(l == r) return a[tree[rt][l]];
		int mlp1 = L==l?0:movel[rt][L-1];
		int mtol = movel[rt][R] - mlp1;
		if(mtol >= k) return query_mid(rt+1, l, mid, mlp1+l, mlp1+mtol-1+l, k);
		else return query_mid(rt+1, mid+1, r, L-l-mlp1+mid+1, L-l-mlp1+(R-L+1-mtol)-1+mid+1, k-mtol);
	}
}dt;

stack<Seg *>S;
void solve(int x) {
	int num = 1;
	Seg * t1 = new Seg(x, x, a[x]);
	while(!S.empty()) {
		Seg * s2 = S.top();
		if(t1->nmid < s2->nmid) {
			t1->nmid = dt.query_mid(1, 0, n-1, s2->l, t1->r, (t1->r-s2->l+1+1)/2); 
			//printf("x = %d nmid = %d %d-> %d
", x+1, t1->nmid, s2->l, t1->r);
			t1->l = s2->l;
			S.pop();
			delete s2;
		}
		else break;
	}
	S.push(t1);
}

bool cmp(const int & lhs, const int & rhs) {
	return a[lhs] < a[rhs];
}

int main() {
	freopen("in", "r", stdin);
	while(scanf("%d", &n) != EOF) {
		for( int i=0; i<n; i++ ) {
			scanf("%d", &a[i]);
			b[i] = i;
		}
		sort(b, b + n, cmp);
		for( int i=0; i<n; i++ ) A[b[i]] = i;
		for( int i=0; i<n; i++ ) tree[0][i] = i;
		dt.build(1, 0, n-1);
		
		for( int i=0; i<n; i++ ) solve(i);
		int k = 0;
		while(!S.empty()) {
			Seg * f = S.top(); S.pop();
			for( int i=0; i<f->r-f->l+1; i++ ) {
				ans[k++] = f->nmid;
			}
		}
		int res = 0;
		for( int i=k-1; i>=0; i-- ) res += abs(ans[i] - a[n-i-1]);

		while(!S.empty()) S.pop();
		for( int i=0; i<n/2; i++ ) swap(a[i], a[n-i-1]);
		for( int i=0; i<n; i++ ) b[i] = i;
		sort(b, b + n, cmp);
		for( int i=0; i<n; i++ ) A[b[i]] = i;

		dt.build(1, 0, n-1);
		for( int i=0; i<n; i++ ) solve(i);
		k = 0;
		while(!S.empty()) {
			Seg * f = S.top(); S.pop();
			for( int i=0; i<f->r-f->l+1; i++ ) {
				ans[k++] = f->nmid;
			}
		}
		int res2 = 0;
		for( int i=k-1; i>=0; i-- ) res2 += abs(ans[i] - a[n-i-1]);
		res = min(res, res2);
		printf("%d
", res);
	}
	return 0;
}

2.3 함수 식 선분 트 리
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <cstdlib>
#include <algorithm>

using namespace std;

const int maxn = 2000 + 10;
#define B printf("BUG
");

int a[maxn], b[maxn];
int ans[maxn];
int n, N;

class Seg {
public :
	int l, r;
	int nmid;
	Seg(int l, int r, int nmid) : l(l), r(r), nmid(nmid) {}
};

class Node {
public :
	Node * ch[2];
	int n;
	Node(int n) : n(n) { ch[0] = ch[1] = NULL; }
	Node() {}
};

class SegTree {
public : 
	Node * tree[maxn];
	void insert(Node *& rt, Node * pre, int l, int r, int x) {
		if(x == 0) {
		}

		if(l == r) {
			if(pre != NULL) rt->n += pre->n;
			rt->n++;
			return ;
		}
		int mid = (l+r)>>1;
		if(x <= mid) { 
			rt->ch[0] = new Node(0);
			if(pre == NULL) insert(rt->ch[0], NULL, l, mid, x);
			else { rt->ch[1] = pre->ch[1]; insert(rt->ch[0], pre->ch[0], l, mid, x); }
		}
		else {
			rt->ch[1] = new Node(0);
			if(pre == NULL) insert(rt->ch[1], NULL, mid+1, r, x);
			else { rt->ch[0] = pre->ch[0]; insert(rt->ch[1], pre->ch[1], mid+1, r, x); }
		}
		rt->n = (rt->ch[0] == NULL ? 0 : rt->ch[0]->n) + (rt->ch[1] == NULL ? 0 : rt->ch[1]->n);
	}

	void build() {
		tree[0] = new Node(0);
		for( int i=1; i<=n; i++ ) {
			tree[i] = new Node(0);
			int x = lower_bound(b, b + N, a[i-1]) - b;
			insert(tree[i], tree[i-1], 0, N-1, x);
		}
	}

	int query(Node * L, Node * R, int l, int r, int k) {
		if(l == r) {
			return b[l];
		}
		int tL = ((L == NULL || L->ch[0] == NULL) ? 0 : L->ch[0]->n);
		int tR = ((R == NULL || R->ch[0] == NULL) ? 0 : R->ch[0]->n);
		int tn = tR - tL;
		if(k <= tn) return query(L==NULL?NULL:L->ch[0], R->ch[0], l, (l+r)/2, k);
		else return query(L==NULL?NULL:L->ch[1], R->ch[1], (l+r)/2 + 1, r, k - tn);
	}

	int query_mid(int L, int R) { //      [L, R]     
		int mid = (R-L+1+1)>>1;
		return query(tree[L], tree[R+1], 0, N-1, mid);
	}
}st;

stack<Seg *>S;
void solve(int x) {
	int num = 1;
	Seg * t1 = new Seg(x, x, a[x]);
	while(!S.empty()) {
		Seg * s2 = S.top();
		if(t1->nmid < s2->nmid) {
			t1->nmid = st.query_mid(s2->l, t1->r); 
			t1->l = s2->l;
			S.pop();
			delete s2;
		}
		else break;
	}
	S.push(t1);
}

int main() {
	//freopen("in", "r", stdin);
	while(scanf("%d", &n) != EOF) {
		for( int i=0; i<n; i++ ) {
			scanf("%d", &a[i]);
			b[i] = a[i];
		}
		sort(b, b + n);
		int tb = unique(b, b + n) - b;
		N = tb;
		st.build();
		for( int i=0; i<n; i++ ) solve(i);
		int k = 0;
		while(!S.empty()) {
			Seg * f = S.top(); S.pop();
			for( int i=0; i<f->r-f->l+1; i++ ) {
				ans[k++] = f->nmid;
			}
		}
		int res = 0;
		for( int i=k-1; i>=0; i-- ) res += abs(ans[i] - a[n-i-1]);

		while(!S.empty()) S.pop();
		for( int i=0; i<n/2; i++ ) swap(a[i], a[n-i-1]);
		st.build();
		for( int i=0; i<n; i++ ) solve(i);
		k = 0;
		while(!S.empty()) {
			Seg * f = S.top(); S.pop();
			for( int i=0; i<f->r-f->l+1; i++ ) {
				ans[k++] = f->nmid;
			}
		}
		int res2 = 0;
		for( int i=k-1; i>=0; i-- ) res2 += abs(ans[i] - a[n-i-1]);
		res = min(res, res2);
		printf("%d
", res);
	}
	return 0;
}
객체 지향 JavaScript — 함수로 작업하기
C 언어 는 산술 표현 식 의 값 을 구한다

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage