Gemini Boy - ACM之路~
树形DP
hdu 1520：http://acm.hdu.edu.cn/showproblem.php?pid=1520
每个节点有权值，子节点和父节点不能同时选，问最后能选的最大价值是多少？
f[u][0]：表示当前节点没选。那么f[u][0] += sum{max(f[v][0], f[v][1]) : v是u的子节点};
f[u][1]；表示当前节点选了。那么f[u][1] += sum{f[v][0] : v是u的子节点};
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 6666;
int f[maxn][2], n, p, q, val, root;
bool vis[maxn];
vector<int> son[maxn];
void dfs(int u) {
for (int i = 0; i < son[u].size(); i++) {
int v = son[u][i];
dfs(v);
f[u][0] += max(f[v][1], f[v][0]);
f[u][1] += f[v][0];
}
}
void work() {
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; i++) {
scanf("%d", &val);
f[i][1] = val;
f[i][0] = 0;
son[i].clear();
}
memset(vis, false, sizeof(vis));
while (scanf("%d %d", &p, &q)) {
if (p == 0 && q == 0)
break;
son[q].push_back(p);
vis[p] = true;
}
for (int i = 1; i <= n; i++) {
if (vis[i] == false) {
root = i; break;
}
}
dfs(root);
printf("%d\n", max(f[root][0], f[root][1]));
}
int main() {
while (~scanf("%d", &n)) {
work();
}
return 0;
}
矩阵连乘问题
POJ 1651：http://poj.org/problem?id=1651
n<=100个数，每次去掉一个数a[i]得到a[i-1]*a[i]*a[i+1]的分数，不能去掉首尾两端，求最小分数。
f(l, r) = min{f(l, k) + f(k+1, r) + a[i-1]*a[k]*a[j] : (l <= k < r)}
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int n, f[111][111], v[111];
int main() {
memset(f, 0, sizeof(f));
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &v[i]);
for (int len = 2; len <= n; len++) {
for (int i = 1; i <= n - len + 1; i++) {
int j = i + len - 1;
f[i][j] = f[i][i] + f[i+1][j] + v[i-1]*v[i]*v[j];
for (int k = i + 1; k < j; k++) {
if (f[i][j] > f[i][k] + f[k+1][j] + v[i-1]*v[k]*v[j])
f[i][j] = f[i][k] + f[k+1][j] + v[i-1]*v[k]*v[j];
}
}
}
printf("%d\n", f[2][n]);
}
spoj MIXTURES：http://www.spoj.com/problems/MIXTURES/
n<=100个数，每次合并两个数a,b，得到新数(a+b)%100，代价是a*b，求并至1个数的最小代价
f(l, r) = min{f(l, k) + f(k+1, r) + mix(l, k)*mix(k+1, r) : l <= k < r} (合并k和k+1), mix(x, y) = (sum[y] - sum[x-1]) % 100;
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, sum[111], val[111], f[111][111];
int getSum(int l, int r) {
return (sum[r] - sum[l-1]) % 100;
}
int main() {
while (~scanf("%d", &n)) {
memset(sum, 0, sizeof(sum));
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; i++) {
scanf("%d", &val[i]);
sum[i] = sum[i-1] + val[i];
}
for (int len = 2; len <= n; len++) {
for (int i = 1; i <= n - len + 1; i++) {
int j = i + len - 1;
f[i][j] = f[i][i] + f[i+1][j] + getSum(i, i) * getSum(i+1, j);
for (int k = i + 1; k < j; k++) {
if (f[i][j] > f[i][k] + f[k+1][j] + getSum(i, k) * getSum(k+1, j))
f[i][j] = f[i][k] + f[k+1][j] + getSum(i, k) * getSum(k+1, j);
}
}
}
printf("%d\n", f[1][n]);
}
}
数位统计
HDU 4705: Y
链接：http://acm.hdu.edu.cn/showproblem.php?pid=4705
题意就是给一棵树，然后问不在一条链上的三个点有多少种。
树形DP，直接求不好求，先求其补集。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#pragma comment(linker, "/STACK:16777216")
const int maxn = 100100;
vector<int> son[maxn];
int f[maxn], x, y;
long long n, ans;
void clear() {
for (int i = 0; i < maxn; i++)
son[i].clear();
memset(f, 0, sizeof(f));
ans = 0;
}
void dfs(int u, int fa) {
long long tmp = 0;
f[u] = 1;
for (int i = 0; i < son[u].size(); i++) {
int v = son[u][i];
if (v == fa)
continue;
dfs(v, u);
f[u] += f[v];
ans += tmp * f[v];
tmp += f[v];
}
ans += tmp * (n - f[u]);
}
void init() {
clear();
for (int i = 1; i < n; i++) {
cin >> x >> y;
son[x].push_back(y);
son[y].push_back(x);
}
}
void work() {
dfs(1, -1);
long long res = n * (n-1) * (n-2) / 6;
cout << res - ans << endl;
}
int main() {
while (cin >> n) {
init();
work();
}
return 0;
}
BZOJ 2733: [HNOI2012]永无乡(平衡树启发式合并)
链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2733
这题我是用treap做的，每个岛代表一个节点，每个节点维护一颗treap，然后节点之间用并查集维护，合并的时候比较俩个节点在并查集中的根的treap的节点个数，从小的向大的暴力insert进去，就行了。0.0
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#include <set>
using namespace std;
template <class T>
inline void scan(T &ret) {
char c; ret = 0;
while ((c = getchar()) < '0' || c > '9')
;
while (c >= '0' && c <= '9')
ret = ret * 10 + (c - '0'), c = getchar();
}
const int maxn = 100100;
struct TreeNode {
TreeNode *L, *R;
int num;
int size;
int pri;
int key;
};
TreeNode nodes[maxn*30], stack[maxn*5];
TreeNode *null;
int C, Top;
void init() {
C = 0; Top = 0;
null = &nodes[C++];
null->L = null->R = null;
null->pri = -0x7FFFFFFF;
null->size = 0;
null->key = 0;
null->num = 0;
}
struct Treap {
TreeNode* root;
vector<TreeNode*> list;
void init() {
root = null;
}
void toArrayList(TreeNode* root) {
if (root != null) {
toArrayList(root->L);
list.push_back(root);
toArrayList(root->R);
}
}
TreeNode* newNode(int key, int num) {
TreeNode* ret;
if (Top)
ret = &stack[--Top];
else ret = &nodes[++C];
ret->L = ret->R = null;
ret->key = key;
ret->pri = rand();
ret->num = num;
ret->size = num;
return ret;
}
TreeNode* merge(TreeNode* small, TreeNode* large) {
if (small == null)
return large;
if (large == null)
return small;
if (small->pri < large->pri) {
small->R = merge(small->R, large);
pushUp(small);
return small;
} else {
large->L = merge(small, large->L);
pushUp(large);
return large;
}
}
pair<TreeNode*, TreeNode*> split(TreeNode* root, int key) {
pair<TreeNode*, TreeNode*> tmp;
if (root == null) {
tmp = make_pair(null, null);
return tmp;
}
if (key <= root->key) {
tmp = split(root->L, key);
root->L = tmp.second;
pushUp(root);
tmp.second = root;
return tmp;
} else {
tmp = split(root->R, key);
root->R = tmp.first;
pushUp(root);
tmp.first = root;
return tmp;
}
}
TreeNode* upperBound(TreeNode* root, int key) {
TreeNode* ans = null;
TreeNode* i = root;
while (i != null) {
if (key < i->key) {
ans = i;
i = i->L;
} else {
i = i->R;
}
}
return ans;
}
TreeNode* lowerBound(TreeNode* root, int key) {
TreeNode* ans = null;
TreeNode* i = root;
while (i != null) {
if (key < i->key) {
i = i->L;
} else {
ans = i;
i = i->R;
}
}
return ans;
}
bool contains(TreeNode* root, int key) {
if (root == null)
return false;
if (key == root->key)
return true;
else if (key < root->key)
return contains(root->L, key);
else
return contains(root->R, key);
}
void insert(TreeNode* root, int key, int num) {
if (key < root->key)
insert(root->L, key, num);
else if (key == root->key)
root->num += num;
else
insert(root->R, key, num);
pushUp(root);
}
void insert(int key, int num) {
if (contains(root, key)) {
insert(root, key, num);
return ;
}
pair<TreeNode*, TreeNode*> tmp = split(root, key);
TreeNode* node = newNode(key, num);
root = merge(merge(tmp.first, node), tmp.second);
}
void del(int key) {
pair<TreeNode*, TreeNode*> tmp = split(root, key);
TreeNode* node = upperBound(tmp.second, key);
if (node == null)
root = tmp.first;
else
root = merge(tmp.first, split(tmp.second, node->key).second);
}
void del(TreeNode* root, int key) {
if (!contains(root, key))
return ;
if (key < root->key)
del(root->L, key);
else if (key == root->key) {
root->num--;
if (root->num == 0)
del(key);
} else {
del(root->R, key);
}
pushUp(root);
}
TreeNode* select(TreeNode* root, int k) {
if (k <= root->L->size)
return select(root->L, k);
else if (k >= root->L->size + 1 && k <= root->L->size + root->num)
return root;
else
return select(root->R, k-root->L->size-root->num);
}
int getMin(TreeNode* root, int key) {
if (key < root->key)
return getMin(root->L, key);
else if (key == root->key)
return root->L->size + root->num;
else
return root->L->size + root->num + getMin(root->R, key);
}
int getMax(TreeNode* root, int key) {
if (key < root->key)
return root->R->size + root->num + getMax(root->L, key);
else if (key == root->key)
return root->R->size + root->num;
else
return getMax(root->R, key);
}
int size() {
return root->size;
}
void visit(TreeNode* root) {
if (root != null) {
printf("key: %d num: %d size: %d\n", root->key, root->num, root->size);
visit(root->L);
visit(root->R);
}
}
void pushUp(TreeNode* x) {
x->size = x->L->size + x->R->size + x->num;
}
};
Treap tree[maxn];
char op[10];
int n, m, q, hash[maxn], arr[maxn];
int par[maxn];
int find(int x) {
if (par[x] != x)
par[x] = find(par[x]);
return par[x];
}
void merge(int x, int y) {
int px = find(x);
int py = find(y);
if (px != py) {
if (tree[px].size() < tree[py].size()) {
par[px] = py;
tree[px].list.clear();
tree[px].toArrayList(tree[px].root);
for (int i = 0; i < tree[px].list.size(); i++) {
TreeNode* tmp = tree[px].list[i];
tree[py].insert(tmp->key, tmp->num);
}
} else {
par[py] = px;
tree[py].list.clear();
tree[py].toArrayList(tree[py].root);
for (int i = 0; i < tree[py].list.size(); i++) {
TreeNode* tmp = tree[py].list[i];
tree[px].insert(tmp->key, tmp->num);
}
}
}
}
int query(int x, int k) {
int px = find(x);
if (tree[px].size() < k)
return -1;
else
return tree[px].select(tree[px].root, k)->key;
}
void work() {
init();
scan(n); scan(m);
// scanf("%d %d", &n, &m);
for (int i = 0; i <= n; i++)
tree[i].init();
for (int i = 0; i <= n; i++)
par[i] = i;
for (int i = 1; i <= n; i++) {
scan(arr[i]);
// scanf("%d", &arr[i]);
hash[arr[i]] = i;
}
for (int i = 1; i <= n; i++)
tree[i].insert(arr[i], 1);
for (int i = 1; i <= m; i++) {
int x, y;
scan(x); scan(y);
// scanf("%d %d", &x, &y);
merge(x, y);
}
}
void run() {
scanf("%d", &q);
for (int i = 1; i <= q; i++) {
int x, y;
scanf("%s", op);
scan(x); scan(y);
// scanf("%s %d %d", op, &x, &y);
if (op[0] == 'Q') {
int ans = query(x, y);
if (ans != -1)
ans = hash[ans];
printf("%d\n", ans);
} else {
merge(x, y);
}
}
}
int main() {
work();
run();
}