Dynamic Programming Optimizations

http://codeforces.com/blog/entry/8219

댓글

댓글 쓰기

이 블로그의 인기 게시물

segment tree

https://www.acmicpc.net/problem/10167 http://www.spoj.com/problems/KQUERY/ http://codeforces.com/contest/380/problem/C -- 정보 http://codeforces.com/blog/entry/15890 http://codeforces.com/blog/entry/15729 struct SegmentTree { int n; vector<int> s; SegmentTree ():n(N),s(N<<2,INT_MAX){} void build (int id=1, int l=0, int r=N-1) { if(r==l){ s[id] = INT_MAX // or a[l]; return; } int mid = (l+r)>>1; build(id<<1, l, mid); build(id<<1|1, mid+1, r); s[id] = min(s[id<<1] , s[id<<1|1]); } void modify (int p, int x, int id=1, int l=0, int r=N-1) { s[id] = min(s[id], x); if(r==l)return; int mid = (l+r)>>1; if(p <= mid) modify(p, x, id<<1, l, mid); else modify(p, x, id<<1|1, mid+1, r); } int query (int x, int y, int id=1, int l=0, int ...
계속 읽기

KOI 2010 세용액

https://en.wikipedia.org/wiki/3SUM https://www.acmicpc.net/problem/2473 https://www.acmicpc.net/problem/2470 3sum problem 주어진 리스트에서 i<j<k이고 a[i] + a[j] + a[k] = X를 만족하는 해가 있는지 찾는 문제. 먼저 주어진 리스트를 정렬한다. O(nlgn) i를 고정시키고 오른쪽 범위에서 a[j] + a[k] = X - a[i]를 만족하는 해가 있는지를 찾는 문제를 생각해보자. 이 문제는 O(n)에 해결 할 수 있다. a[j] + a[k] > X - a[i]라면 k를 1 감소 시키고 그 외는 j를 1 증가시킨다. 이러면 O(n)에 만족하는 j, k 를 찾을 수 있다. i를 1씩 증가시키면서 모든 구간에 대해 반복하면 최종적으로 O(n^2)에 답을 찾을 수 있다.
계속 읽기