A. 录制唱片

#include <bits/stdc++.h>
using namespace std;
int dp[25][25][25], A[25];
void Check(int &a, int b) {
    if (a < b)
        a = b;
}
int main() {
    int n, t, m, c = 0;
    cin >> n >> t >> m;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &A[i]);
        if (A[i] <= t)
            A[++c] = A[i];
    }
    n = c;
    for (int i = 0; i < n; i++)
        for (int j = 1; j <= m; j++)
            for (int k = 0; k <= t; k++) {
                //刷表
                int p = A[i + 1];
                Check(dp[i + 1][j][k], dp[i][j][k]);  //不取
                if (k + p <= t)
                    Check(dp[i + 1][j][k + p], dp[i][j][k] + 1);
                else if (j < m)
                    Check(dp[i + 1][j + 1][p], dp[i][j][k] + 1);
            }
    int ans = 0;
    for (int j = 0; j <= t; j++) Check(ans, dp[n][m][j]);
    printf("%d\n", ans);
    return 0;
}

B. 路短最

int n, m, dis[20][20], dp[1 << 20][20], ans;

int main() {
    memset(dp, 0x8f, sizeof dp);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int s, d, l;
        cin >> s >> d >> l;
        dis[s][d] = l;
    }
    dp[1][0] = 0;
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            if ((i >> j) & 1) {
                for (int k = 0; k < n; k++) {
                    if (((i >> k) & 1) && dis[j][k]) {
                        dp[i][k] = max(dp[i][k], dp[i - (1 << k)][j] + dis[j][k]);
                    }
                }
            }
        }
    }
    for (int i = 0; i < (1 << n); i++) {
        if ((i & 1) && ((i >> (n - 1)) & 1)) {
            ans = max(ans, dp[i][n - 1]);
        }
    }
    cout << ans;

    return 0;
}

POI2012 Cloakroom

充分利用状态转移和定义

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 1, M = 1e5 + 1, T = 1e6 + 1;
struct node {
    int a, b, c;
    friend bool operator<(node a, node b) { return a.a < b.a; }
} t[N];
int n, q, f[M];
struct nod {
    int m, k, s, id;
    friend bool operator<(nod a, nod b) { return a.m < b.m; }
} a[T];
bool ff[T];
int main() {
    cin >> n;
    int ma = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &t[i].c, &t[i].a, &t[i].b);
        ma += t[i].c;
    }
    ma = min(ma, M - 1);
    sort(t + 1, t + 1 + n);
    cin >> q;
    for (int i = 1; i <= q; i++) {
        scanf("%d%d%d", &a[i].m, &a[i].k, &a[i].s);
        a[i].id = i;
    }
    sort(a + 1, a + 1 + q);
    int k = 1;
    for (int i = 1; i <= n && k <= q; i++) {
        while (t[i].a > a[k].m && k <= q) {
            if (f[a[k].k] > a[k].m + a[k].s)
                ff[a[k].id] = true;
            k++;
        }
        for (int j = ma; j; j--) {
            if (j > t[i].c)
                f[j] = max(f[j], min(f[j - t[i].c], t[i].b));
            else if (j == t[i].c)
                f[j] = max(f[j], t[i].b);
        } /*
         for(int j=1;j<=ma;j++)cout<<f[j]<<" ";
         cout<<"|\n";*/
    }
    while (k <= q) {
        if (f[a[k].k] > a[k].m + a[k].s)
            ff[a[k].id] = true;
        k++;
    }
    for (int i = 1; i <= q; i++) {
        if (ff[i])
            printf("TAK\n");
        else
            printf("NIE\n");
    }
    return 0;
}

D. 奶牛看电影

状态压缩积累就好了

using namespace std;
const int N = 1 << 22;
int dp[N], n, L, val[30], ans = 0x3f3f3f3f;
vector<int> ve[30];
int cont(int x) {
    int cnt = 0;
    while (x) cnt += x & 1, x >>= 1;
    return cnt;
}
int main() {
    scanf("%d%d", &n, &L);
    for (int i = 0; i < n; i++) {
        int num, x;
        scanf("%d%d", &val[i], &num);
        for (int j = 1; j <= num; j++) {
            scanf("%d", &x);
            ve[i].push_back(x);
        }
    }
    for (int now = 0; now < (1 << n); now++) {
        if (dp[now] >= L)
            ans = min(ans, cont(now));
        for (int j = 0; j < n; j++)
            if (!((now >> j) & 1)) {
                int t = upper_bound(ve[j].begin(), ve[j].end(), dp[now]) - ve[j].begin() - 1;
                if (t >= 0)
                    dp[now + (1 << j)] = max(dp[now | (1 << j)], ve[j][t] + val[j]);
            }
    }
    if (ans == 0x3f3f3f3f)
        puts("-1");
    else
        printf("%d\n", ans);
    return 0;
}