Blank

/* 线性dp、区间dp
一、f[cur][i][j][k][q]
    1.表示前cur个空格，i、j、k、q分别表示0、1、2、3最后出现的位置
    2.
        第cur + 1个位置放0：f[cur + 1][cur + 1][j][k][q] += f[cur][i][j][k][q];
        第cur + 1个位置放1：f[cur + 1][i][cur + 1][k][q] += f[cur][i][j][k][q];
        第cur + 1个位置放2：f[cur + 1][i][j][cur + 1][q] += f[cur][i][j][k][q];
        第cur + 1个位置放3：f[cur + 1][i][j][k][cur + 1] += f[cur][i][j][k][q];
    3.限制条件
        cur一定能取到r，比较一下i、j、k、q跟l的大小
    4.时间O(n ^ 5), 空间O(n ^ 5)
二、优化
    ①：f[i][j][k][q]（i <= j <= k <= q）
        1.表示不同数字最后出现的位置
        2.
            f[j][k][q][q + 1] += f[i][j][k][q];
            f[i][k][q][q + 1] += f[i][j][k][q];
            f[i][j][q][q + 1] += f[i][j][k][q];
            f[i][j][k][q + 1] += f[i][j][k][q];
        3.时间O(n ^ 4), 空间O(n ^ 4)
    ②：滚动数组
        1.f[i][j][k][2]（i <= j <= k）
        2.
            f[j][k][cur - 1][now] += f[i][j][k][pre];
            f[i][k][cur - 1][now] += f[i][j][k][pre];
            f[i][j][cur - 1][now] += f[i][j][k][pre];
            f[i][j][k][now] += f[i][j][k][pre];
        3.时间O(n ^ 4), 空间O(2 * n ^ 3)
*/

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
const int N = 110;
const LL mo = 998244353;

int n, m;
vector<PII> v[N];

void qmo(int &x) {
    if (x >= mo)
        x -= mo;
}

int main() {
    int T;
    scanf("%d", &T);

    while (T -- ) {

        scanf("%d%d", &n, &m);

        for (int i = 1; i <= n; i ++ )

            v[i].clear();
        int l, r, x;

        for (int i = 1; i <= m; i ++ ) {

            scanf("%d%d%d", &l, &r, &x);
            v[r].push_back(make_pair(l, x));
        }

        int now = 1;
        int f[N][N][N][2] = {0};
        f[0][0][0][0] = 1;

        for (int cur = 1; cur <= n; cur ++, now ^= 1) {

            for (int k = 0; k <= cur; k ++ )

                for (int j = 0; j <= k; j ++ )

                    for (int i = 0; i <= j; i ++ ) {

                        qmo(f[j][k][cur - 1][now] += f[i][j][k][now ^ 1]);
                        qmo(f[i][k][cur - 1][now] += f[i][j][k][now ^ 1]);
                        qmo(f[i][j][cur - 1][now] += f[i][j][k][now ^ 1]);
                        qmo(f[i][j][k][now] += f[i][j][k][now ^ 1]);
                        f[i][j][k][now ^ 1] = 0;
                    }

            for (int k = 0; k < cur; k ++ )

                for (int j = 0; j <= k; j ++ )

                    for (int i = 0; i <= j; i ++ )

                        for (auto x : v[cur]) {
                            if ((1 + (i >= x.first) + (j >= x.first) + (k >= x.first)) != x.second)
                                f[i][j][k][now] = 0;
                        }
        }

        int ans = 0;
        now ^= 1;

        for (int k = 0; k < n; k ++ )

            for (int j = 0; j <= k; j ++ )

                for (int i = 0; i <= j; i ++ )

                    qmo(ans += f[i][j][k][now]);
        printf("%d\n", ans);
    }

    return 0;
}

Employment Planning

/*
f[i][j]:表示前i个月且第i个月雇佣j个人的最小花费
*/
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

int f[20][N];
int n;
int gj, gz, jg;
int sum[20];

int main() {
    while (~scanf("%d", &n)) {
        if (n == 0)
            break;
        scanf("%d%d%d", &gj, &gz, &jg);
        int MAX = 0;

        for (int i = 1; i <= n; i ++ ) {

            scanf("%d", &sum[i]);
            MAX = max(MAX, sum[i]);
        }

        memset(f, 0, sizeof f);

        for (int i = sum[1]; i <= MAX; i ++ )

            f[1][i] = i * (gj + gz);

        for (int i = 2; i <= n; i ++ ) {

            for (int j = sum[i]; j <= MAX; j ++ ) { // 当前月份可能雇佣的人数

                int min_price = INF;

                for (int k = sum[i - 1]; k <= MAX; k ++ ) { // 上一个月可能雇佣的人数

                    int s = 0;

                    if (k >= j)
                        s = f[i - 1][k] + (k - j) * jg + j * gz;
                    else
                        s = f[i - 1][k] + (j - k) * gj + j * gz;
                    min_price = min(min_price, s);
                }

                f[i][j] = min_price;
            }
        }

        int ans = INF;

        for (int i = sum[n]; i <= MAX; i ++ )

            ans = min(ans, f[n][i]);
        printf("%d\n", ans);
    }

    return 0;
}

A Task Process

/*
f[i][j]:表示前i个人做了j件任务A的情况下，还能完成多少件任务B
*/
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 60, INF = 0x3f3f3f3f;

int n;
int x, y;
int a[N], b[N];
int f[N][210];
int casei;

bool check(int mid) {
    memset(f, -1, sizeof f);

    for (int j = 0; j <= x && j * a[1] <= mid; j ++ )

        f[1][j] = (mid - j * a[1]) / b[1];

    for (int i = 2; i <= n; i ++ )

        for (int j = 0; j <= x; j ++ )

            for (int k = 0; k <= j && k * a[i] <= mid; k ++ )

                if (f[i - 1][j - k] != -1)
                    f[i][j] = max(f[i][j], f[i - 1][j - k] + (mid - k * a[i]) / b[i]);

    if (f[n][x] >= y)
        return true;
    return false;
}

int main() {
    int T;
    scanf("%d", &T);

    while (T -- ) {
        scanf("%d%d%d", &n, &x, &y);

        for (int i = 1; i <= n; i ++ )

            scanf("%d%d", &a[i], &b[i]);
        int l = 0, r = INF;
        int ans = 0;

        while (l < r) {
            int mid = l + r >> 1;

            if (check(mid)) {
                ans = mid;
                r = mid;
            } else
                l = mid + 1;
        }

        printf("Case %d: %d\n", ++ casei, ans);
    }

    return 0;
}

World Cup Noise

/*
f[i]:表示长度为i的序列合法的情况
    1.第i位放0:f[i] += f[i - 1]
    2.第i位放1:f[i] += f[i - 2]
*/
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 50;

int f[N];
int n;
int casei;

void init() {
    f[0] = 0, f[1] = 2, f[2] = 3;

    for (int i = 3; i < N; i ++ )

        f[i] = f[i - 1] + f[i - 2];
}

int main() {
    init();
    int T;
    scanf("%d", &T);

    while (T -- ) {
        scanf("%d", &n);
        printf("Scenario #%d:\n", ++ casei);
        printf("%d\n\n", f[n]);
    }

    return 0;
}