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 '9') tmp = getchar();
while (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 '9') tmp = getchar();
while (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 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 = 0; j--) {
for (int k = 0; k = 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 '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的计数题真的很烦。 还是自己太弱，连最小费用最大流都不会写，感觉吃枣药丸。