AtCoder Educational DP Contest

A

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, k;
int f[N], a[N];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for(int i = 2; i <= n; ++i) {
        f[i] = 0x3f3f3f3f;
        if(i >= 2) f[i] = min(f[i], f[i - 1] + abs(a[i] - a[i - 1]));
        if(i >= 3) f[i] = min(f[i], f[i - 2] + abs(a[i] - a[i - 2]));
    }
    printf("%d\n", f[n]);
}

B

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, k;
int f[N], a[N];

int main() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for(int i = 2; i <= n; ++i) {
        f[i] = 0x3f3f3f3f;
        for(int j = max(i - k, 1); j < i; ++j) {
            f[i] = min(f[i], f[j] + abs(a[i] - a[j]));
        }
    }
    printf("%d\n", f[n]);
}

C

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, k;
int f[N][3], a[N][3];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d%d%d", &a[i][0], &a[i][1], &a[i][2]);
    for(int i = 1; i <= n; ++i) {
        for(int j = 0; j < 3; ++j) {
            for(int k = 0; k < 3; ++k) {
                if(j == k) continue;
                f[i][j] = max(f[i][j], f[i - 1][k] + a[i][j]);
            }
        }
    }
    printf("%d\n", max(max(f[n][0], f[n][1]), f[n][2]));
}

D

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 100010;

int n, W;
ll f[N], w[N], v[N];

int main() {
    scanf("%d%d", &n, &W);
    ll ans = 0;
    for(int i = 1; i <= n; ++i) scanf("%lld%lld", &w[i], &v[i]);
    for(int i = 1; i <= n; ++i) {
        for(int j = W; j >= w[i]; --j) {
            f[j] = max(f[j], f[j - w[i]] + v[i]);
        }
    }
    for(int i = 1; i <= W; ++i) ans = max(ans, f[i]);
    printf("%lld\n", ans);
}

E

对比前面四题不那么傻的一题
很妙的一个转化，注意到这题的\(W\)很大，但是\(v\)很小，所以不妨转换一下状态，设\(f[i,j]\)表示前\(i\)个物品，选出后的总价值为\(j\)，需要的最小体积。那么有\(f[i][j]=\min\{f[i-1][j-v[i]]+w[i]\}\)，答案就是对于所有\(f[n][j]\le W\)的\(j\)取\(\max\)。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 100010;

int n, v[N], W, w[N];
int f[110][N];

int main() {
    scanf("%d%d", &n, &W);
    int sum = 0;
    for(int i = 1; i <= n; ++i) scanf("%d%d", &w[i], &v[i]), sum += v[i];
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    int ans = 0;
    for(int i = 1; i <= n; ++i) {
        for(int j = 0; j <= sum; ++j) {
            if(j >= v[i]) f[i][j] = min(f[i][j], f[i - 1][j - v[i]] + w[i]);
            f[i][j] = min(f[i][j], f[i - 1][j]);
            if(f[i][j] <= W) ans = max(ans, j);
        }
    }
    printf("%d\n", ans);
}

F

LCS做一下就好，输出方案的话从\([n,m]\)往回找就好了，用个栈压一下答案。

#include <bits/stdc++.h>
using namespace std;

const int N = 3010;

char s[N], t[N], st[N];
int f[N][N];

int main() {
    scanf("%s%s", s + 1, t + 1);
    int n = strlen(s + 1), m = strlen(t + 1);
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if(s[i] == t[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }
    }
    int now = f[n][m] + 1;
    int top = 0;
    for(int i = n; i; --i) {
        for(int j = m; j; --j) {
            if(s[i] == t[j] && f[i][j] == now - 1) {
                --now;
                st[++top] = s[i];
                break;
            }
        }
    }
    while(top) putchar(st[top--]);
}

G

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, m, deg[N], q[N], f[N];
int cnt, head[N];
struct edge { int to, nxt; } e[N];

void ins(int u, int v) {
    e[++cnt] = (edge) { v, head[u] };
    head[u] = cnt;
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1, u, v; i <= m; ++i) {
        scanf("%d%d", &u, &v);
        ins(u, v); deg[v]++;
    }
    int l = 1, r = 1;
    for(int i = 1; i <= n; ++i) {
        if(!deg[i]) q[r++] = i;
    }
    while(l < r) {
        int u = q[l++];
        for(int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            f[v] = max(f[v], f[u] + 1);
            deg[v]--;
            if(!deg[v]) q[r++] = v;
        }
    }
    int ans = 0;
    for(int i = 1; i <= n ;++i) ans = max(ans, f[i]);
    printf("%d\n", ans);
    return 0;
}

H

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
const int mod = 1e9 + 7;

int h, w, f[N][N];
char a[N][N];

int main() {
    scanf("%d%d", &h, &w);
    f[1][1] = 1;
    for(int i = 1; i <= h; ++i) scanf("%s", a[i] + 1);
    for(int i = 1; i <= h; ++i) {
        for(int j = 1; j <= w; ++j) {
            if(i == 1 && j == 1) continue;
            if(a[i][j] == '.' && a[i - 1][j] == '.')
                (f[i][j] += f[i - 1][j]) %= mod;
            if(a[i][j] == '.' && a[i][j - 1] == '.')
                (f[i][j] += f[i][j - 1]) %= mod;
        }
    }
    printf("%d\n", f[h][w]);
}

I

#include <bits/stdc++.h>
using namespace std;

const int N = 3000;

int n;
double p[N], f[2][N];

int main() {
    scanf("%d", &n);
    int cur = 0;
    for(int i = 1; i <= n; ++i) scanf("%lf", &p[i]);
    f[1][0] = 1;
    for(int i = 1; i <= n; ++i) {
        memset(f[cur], 0, sizeof(f[cur]));
        for(int j = 0; j <= i; ++j) {
            f[cur][j] += f[cur ^ 1][j] * (1 - p[i]);
            f[cur][j] += f[cur ^ 1][j - 1] * p[i];
        }
        cur ^= 1;
    }
    double ans = 0;
    for(int i = n / 2 + 1; i <= n; ++i) ans += f[cur ^ 1][i];
    printf("%.15lf\n", ans);
}

J

设\(f[i][j][k]\)表示当前\(a_x=3\)的数有\(i\)个，\(=2\)的有\(j\)个，\(=3\)的有\(k\)个。
则有方程
\[f[i][j][k]=\frac {\left( 1+f[i-1][j+1][k]*\frac i n+f[i][j-1][k+1] * \frac j n + f[i][j][k-1]* \frac k n \right)}{\frac {i+j+k} n}\]
答案即为\(f[cnt[3]][cnt[2]][cnt[1]]\)

#include <bits/stdc++.h>
using namespace std;

const int N = 310;

double f[N][N][N];
int n, a[N], cnt[5];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]), cnt[a[i]]++;
    for(int i = 0; i <= n; ++i) {
        for(int j = 0; j <= n; ++j) {
            for(int k = 0; k <= n; ++k) {
                if(i + j + k > n) continue;
                if(!i && !j && !k) continue;
                if(i > cnt[3]) continue;
                if(j > cnt[3] + cnt[2]) continue;
                if(k > cnt[3] + cnt[2] + cnt[1]) continue;
                double p1 = 1.0 * i / n, p2 = 1.0 * j / n, p3 = 1.0 * k / n;
                double p4 = 1.0 * (i + j + k) / n;
                f[i][j][k] = (double)(1+(i?f[i-1][j+1][k]:0)*p1+(j?f[i][j-1][k+1]:0)*p2+(k?f[i][j][k-1]:0)*p3)/p4;
            }
        }
    }
    printf("%.10lf\n", f[cnt[3]][cnt[2]][cnt[1]]);
}