woc…这Onedrive好辣鸡啊。。。访问速度真是不敢恭维，强烈建议下载后查看此PPT。 算法什么的PPT里都有，直接贴代码吧。 T1:
#include#include #include #include #include #define LL long long using namespace std; int a[55], cnt[10]; int len; void get_line(int *t) { char tmp = getchar(); while (tmp < '0' || tmp > '9') tmp = getchar(); while (tmp <= '9' && tmp >= '0') { t[++len] = tmp - '0'; cnt[t[len]]++; tmp = getchar(); } } LL calc() { LL ans = 1; int num = 0; for (int i = 0; i <= 9; i++) { for (int j = 1; j <= cnt[i]; j++) { ans *= (++num); ans /= j; } } return ans; } int main() { #ifndef LOCAL freopen("perm.in", "r", stdin); freopen("perm.out", "w", stdout); #endif get_line(a); int num; LL ans = 0; for (int i = 1; i <= len; i++) { num = a[i]; for (int j = 0; j < num; j++) { if (!cnt[j]) continue; cnt[j]--; ans += calc(); cnt[j]++; } cnt[num]--; } printf("%lld\n", ans); return 0; }
T2:
#include#include #include #include #define LL long long using namespace std; const int MX = 50005; int m, b, h, n; int a[MX], hi[MX], cost[MX]; int sum, tot; class node{ public: int c, tar; }ns[MX]; inline bool cmp(node a, node b) { return a.c < b.c; } const inline int get_num() { int aa = 0; char tmp = getchar(); while (tmp < '0' || tmp > '9') tmp = getchar(); while (tmp <= '9' && tmp >= '0') { aa = aa * 10 + tmp - '0'; tmp = getchar(); } return aa; } int Main() { #ifndef LOCAL freopen("factory1.in", "r", stdin); freopen("factory1.out", "w", stdout); #endif m = get_num(); b = get_num(); h = get_num(); n = get_num(); for (int i = 1; i <= m; i++) { a[i] = get_num(); sum += a[i]; } for (int i = 1; i <= n; i++) { hi[i] = get_num(); } for (int i = 1; i <= m; i++) { cost[i] = get_num(); tot += cost[i] * a[i]; } int pos; LL ans = 0x7fffffff, now, le; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { ns[j].tar = j; ns[j].c = get_num() - cost[j]; } sort(ns + 1, ns + m + 1, cmp); now = tot, le = sum - b; for (int j = 1; j <= m; j++) { if (le > a[ns[j].tar]) { le -= a[ns[j].tar]; now += a[ns[j].tar] * ns[j].c; } else { now += le * ns[j].c; break; } } if (now + hi[i] < ans) { ans = now + hi[i]; pos = i; } } printf("%d\n%lld\n", pos, ans + h); return 0; } int AA = Main(); int main() {;}
T3:
#include#include #include #include using namespace std; const int MX = 205; int m, n; int dfn[MX], low[MX]; int v[MX], w[MX]; int suv[MX], suw[MX]; int in[MX]; int f[105][505]; class edge{ public: int to, ne; }e[MX], e2[MX]; int _tot, _head[MX], tot, head[MX]; class stack_{ private: int st[MX], tp, _in[MX]; public: bool instack(int x) { return _in[x]; } void push(int x) { st[++tp] = x; _in[x]++; } void pop() { _in[st[tp--]]--; } int top() { return st[tp]; } }s; void addedge(int a, int b) { //e[++tot].fr = a; e[++tot].to = b; e[tot].ne = head[a]; head[a] = tot; } void addedge2(int a, int b) { in[b]++; //e2[++tot].fr = a; e2[++tot].to = b; e2[tot].ne = _head[a]; _head[a] = tot; } int belong[MX]; int cnt, kcnt; void tarjan(int x) { int now = 0; dfn[x] = low[x] = ++cnt; s.push(x); for (int i = head[x]; i; i = e[i].ne) { if (!dfn[e[i].to]) { tarjan(e[i].to); low[x] = min(low[x], low[e[i].to]); } else if (s.instack(e[i].to)) { low[x] = min(low[x], dfn[e[i].to]); } } if (low[x] == dfn[x]) { kcnt++; while (now != x) { now = s.top(); s.pop(); belong[now] = kcnt; suv[kcnt] += v[now]; suw[kcnt] += w[now]; } } } void rebuild() { tot = 0; for (int i = 1; i <= n; i++) { for (int j = head[i]; j; j = e[j].ne) { if (belong[e[j].to] != belong[i]) { addedge2(belong[i], belong[e[j].to]); } } } } void dp(int x) { for (int i = _head[x]; i; i = e2[i].ne) { dp(e2[i].to); for (int j = m - suw[x]; j >= 0; j--) { for (int k = 0; k <= j; k++) { f[x][j] = max(f[x][j], f[x][k] + f[e2[i].to][j - k]); } } } for (int i = m; i >= 0; i--) { if (i >= suw[x]) f[x][i] = f[x][i - suw[x]] + suv[x]; else f[x][i] = 0; } } int main() { #ifndef LOCAL freopen("install.in", "r", stdin); freopen("install.out", "w", stdout); #endif scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &w[i]); } for (int i = 1; i <= n; i++) { scanf("%d", &v[i]); } int x; for (int i = 1; i <= n; i++) { scanf("%d", &x); if (x) { addedge(x, i); } } for (int i = 1; i <= n; i++) { if (!dfn[i]) tarjan(i); } rebuild(); for (int i = 1; i <= kcnt; i++) { if (!in[i]) { addedge2(kcnt + 1, i); } } dp(kcnt + 1); printf("%d\n", f[kcnt + 1][m]); return 0; }
T4:
#include#include #include #include #define LL long long using namespace std; const int chenyao = 1e8; int f[5005][5005], g[5005][5005]; char a[5005], b[5005]; int l1, l2; int get_line(char *tar) { int len = 0; char tmp = getchar(); while (tmp < 'A' || tmp > 'Z') tmp = getchar(); while (tmp != '.') { tar[++len] = tmp; tmp = getchar(); } return len; } int main() { #ifndef LOCAL freopen("lcs.in", "r", stdin); freopen("lcs.out", "w", stdout); #endif l1 = get_line(a); l2 = get_line(b); for (int i = 0; i < max(l1, l2); i++) g[0][i] = g[i][0] = 1; for (int i = 1; i <= l1; i++) { for (int j = 1; j <= l2; j++) { if (a[i] == b[j]) { f[i][j] = f[i - 1][j - 1] + 1; g[i][j] += g[i - 1][j - 1]; if (f[i][j - 1] == f[i][j]) g[i][j] += g[i][j - 1]; if (f[i - 1][j] == f[i][j]) g[i][j] += g[i - 1][j]; } else { f[i][j] = max(f[i][j - 1], f[i - 1][j]); if (f[i - 1][j] == f[i][j]) g[i][j] += g[i - 1][j]; if (f[i][j - 1] == f[i][j]) g[i][j] += g[i][j - 1]; if (f[i][j - 1] == f[i - 1][j] && f[i][j] == f[i - 1][j - 1]) g[i][j] -= g[i - 1][j - 1]; } g[i][j] = g[i][j] % chenyao; } } printf("%d\n%d\n", f[l1][l2], g[l1][l2]); }
T5:
#include#include #include #include using namespace std; const int INF = 1e9 + 7; int n, m, s; int f[55][10005]; int u[55]; int d[55]; int main() { #ifndef LOCAL freopen("order.in", "r", stdin); freopen("order.out", "w", stdout); #endif scanf("%d%d%d", &n, &m, &s); for (int i = 1; i <= n; i++) { scanf("%d", &u[i]); } for (int i = 1; i <= n; i++) { scanf("%d", &d[i]); } for (int i = 1; i <= s; i++) f[0][i] = INF; for (int i = 1; i <= n; i++) { int tmp = INF, k = 0; for (int j = 0; j <= s; j++) { for (; k <= min(u[i] + j, s); k++) tmp = min(tmp, f[i - 1][k] + k * (m - d[i])); f[i][j] = tmp + (u[i] + j) * d[i]; } } printf("%d\n", f[n][0]); return 0; }
总结一下，HAOI2010的题不算很难，但是奇怪的DP和需要用到DP的计数题真的很烦。 还是自己太弱，连最小费用最大流都不会写，感觉吃枣药丸。