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]);
}
}
数位统计
19th Polish Olympiad in Informatics
链接：http://main.edu.pl/en/archive/oi/19
Festival(Stage I)：
Description
有n个正整数X1,X2,...,Xn，再给出m1+m2个限制条件，限制分为两类：
1. 给出a,b (1<=a,b<=n)，要求满足Xa + 1 = Xb
2. 给出c,d (1<=c,d<=n)，要求满足Xc <= Xd
在满足所有限制的条件下，求集合{Xi}大小的最大值。
Input
第一行三个正整数n, m1, m2 (2<=n<=600, 1<=m1+m2<=100,000)。
接下来m1行每行两个正整数a,b (1<=a,b<=n)，表示第一类限制。
接下来m2行每行两个正整数c,d (1<=c,d<=n)，表示第二类限制。
Output
一个正整数，表示集合{Xi}大小的最大值。
如果无解输出NIE。
Sample Input
4 2 2
1 2
3 4
1 4
3 1
Sample Output
3
Hint
X3=1, X1=X4=2, X2=3
这样答案为3。容易发现没有更大的方案。
做法就是类似于差分约束建图，然后在每个scc里判断是否满足限制条件。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int maxn = 1000;
const int inf = 1000000000;
struct Edge {
int v, w;
Edge() {}
Edge(int vv, int ww) {
v = vv; w = ww;
}
};
vector<Edge> adj[maxn*2];
int idx, size;
int n, m1, m2, a, b;
int dist[maxn][maxn];
int dfn[maxn], low[maxn], stk[maxn], id[maxn];
bool vis[maxn];
stack<int> S;
inline int Myabs(int x) {
if (x < 0)
x = -x;
return x;
}
void addEdge(int u, int v, int w) {
adj[u].push_back(Edge(v, w));
}
void tarjan(int u) {
dfn[u] = low[u] = ++idx;
S.push(u); vis[u] = true;
vector<Edge>::iterator it;
for (it = adj[u].begin(); it != adj[u].end(); it++) {
int v = it->v;
if (dfn[v] == -1) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (vis[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {
size++;
int v;
do {
v = S.top();
S.pop();
id[v] = size;
vis[v] = false;
} while (u != v);
}
}
void clearAll() {
for (int i = 0; i < maxn; i++)
adj[i].clear();
memset(dfn, -1, sizeof(dfn));
memset(low, -1, sizeof(low));
memset(vis, false, sizeof(vis));
memset(id, 0, sizeof(id));
memset(dist, 0, sizeof(dist));
while (!S.empty()) S.pop();
}
void init() {
scanf("%d %d %d", &n, &m1, &m2);
for (int i = 0; i < m1; i++) {
scanf("%d %d", &a, &b);
addEdge(a, b, 1);
addEdge(b, a, -1);
}
for (int i = 0; i < m2; i++) {
scanf("%d %d", &a, &b);
addEdge(a, b, 0);
}
void work() {
for (int i = 1; i <= n; i++) {
if (dfn[i] == -1)
tarjan(i);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j)
dist[i][j] = 0;
else
dist[i][j] = -inf;
}
}
for (int i = 1; i <= n; i++) {
vector<Edge>::iterator it;
for (it = adj[i].begin(); it != adj[i].end(); it++) {
int j = it->v;
if (id[i] == id[j])
dist[i][j] = max(dist[i][j], it->w);
}
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
if (dist[i][k] <= -inf)
continue;
for (int j = 1; j <= n; j++) {
if (dist[k][j] <= -inf)
continue;
if (dist[i][k] + dist[k][j] > dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
for (int i = 1; i <= n; i++) {
if (dist[i][i] > 0) {
puts("NIE");
return ;
}
}
int result = 0;
vector<int> ans;
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++) {
ans.clear();
if (vis[i] == true)
continue;
for (int j = 1; j <= n; j++) {
if (id[i] == id[j]) {
vis[j] = true;
ans.push_back(j);
}
}
int tmp = 0;
for (int j = 0; j < ans.size(); j++) {
for (int k = 0; k < ans.size(); k++) {
tmp = max(tmp, Myabs(dist[ans[j]][ans[k]])+1);
}
}
result += tmp;
}
printf("%d\n", result);
}
int main() {
clearAll();
init();
work();
return 0;
}
Letters(Stage I)：
Description
给出两个长度相同且由大写英文字母组成的字符串A、B，保证A和B中每种字母出现的次数相同。
现在每次可以交换A中相邻两个字符，求最少需要交换多少次可以使得A变成B。
Input
第一行一个正整数n (2<=n<=1,000,000)，表示字符串的长度。
第二行和第三行各一个长度为n的字符串，并且只包含大写英文字母。
Output
一个非负整数，表示最少的交换次数。
Sample Input
3
ABC
BCA
Sample Output
2
Hint
ABC -> BAC -> BCA
其实就是求逆序对。BIT维护。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 1001000;
char str1[maxn], str2[maxn];
vector<int> adj1[maxn], adj2[maxn];
int len, sum[maxn], pos[maxn];
int main() {
scanf("%d %s %s", &len, str1, str2);
for (int i = 0; i < len; i++) {
adj1[str1[i]-'A'].push_back(i);
adj2[str2[i]-'A'].push_back(i);
}
for (int i = 0; i < 26; i++) {
for (int j = 0; j < adj1[i].size(); j++) {
pos[adj1[i][j]] = adj2[i][j];
}
}
long long ans = 0;
for (int i = len - 1; i >= 0; i--) {
for (int j = pos[i]; j; j -= j & -j)
ans += sum[j];
for (int j = pos[i] + 1; j <= len; j += j & -j)
sum[j]++;
}
printf("%lld\n", ans);
return 0;
}
2013 ACM/ICPC Asia Regional Online —— Warmup
A题(HDU 4706)：无意义的题，就贴个代码吧
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
void get(int x, int n) {
int y = x + 2 * (n - 1);
y %= 26;
for (int i = 1; i <= n; i++) {
printf("%c", 'a'+(x+i-1)%26);
for (int j = n-i-1; j >= 1; j--)
printf(" ");
if (i > 1 && i < n)
printf("%c", 'a'+(y+1-i+26)%26);
for (int j = 1; j <= i-2; j++)
printf(" ");
printf("%c\n", 'a'+(y+i-1)%26);
}
}
int main() {
int x = 0;
for (int i = 3; i <= 10; i++) {
get(x, i);
x = (x+2*i+i-2) % 26;
}
return 0;
}