2025 社团招新 · 方案一状态计数DP

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 3/5 · 共 2015 字

dp[x][y] 记两部门人数逐人转移，O(n^3) 部分分

2025
贪心

正文

// CSP-S 2025 复赛 T1 · 社团招新（方案一：状态 DP，n ≤ 500 部分分）
// 原题：https://oj.yecheng.tv/p/2466
// 题意：T 组数据。n 个人、3 个部门，每人对三部门各有一个满意度，
// 每人必须进一个部门，每部门人数不得超过 n/2（n 保证为偶数），
// 最大化满意度总和。
// （本题在 OJ 上为标准输入输出，无需文件重定向。）
// 思路：
//   最直接的计数型 DP：dp[x][y] = 已处理若干人、部门 1 有 x 人、
//   部门 2 有 y 人（部门 3 人数可由总数推出）时的最大满意度。
//   逐人转移：这个人进三个部门之一，目标部门人数超过 n/2 则剪掉。
//   全部处理完后，所有可达状态里取最大值即答案。
//   用滚动数组压掉「人数」那一维。
// 复杂度：每组 O(n · (n/2)^2 · 3)，n ≤ 500 可过，n = 5000 超时；
//   满分见方案二的贪心。
// 易错点：
//   1. 部门 3 的人数 = i - x - y，转移时同样要检查上限；
//   2. 不可达状态用 -1 标记，取答案时跳过；
//   3. 满意度可达 1e9，用 long long。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        vector<array<ll, 3>> a(n);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < 3; j++) scanf("%lld", &a[i][j]);
        int h = n / 2;
        const ll NEG = -1;
        vector<vector<ll>> dp(h + 1, vector<ll>(h + 1, NEG)), nd(h + 1, vector<ll>(h + 1, NEG));
        dp[0][0] = 0; // x=部门1人数, y=部门2人数
        for (int i = 0; i < n; i++) {
            for (int x = 0; x <= h; x++) nd[x].assign(h + 1, NEG);
            for (int x = 0; x <= h; x++)
                for (int y = 0; y <= h; y++) {
                    if (dp[x][y] < 0) continue;
                    int z = i - x - y;
                    if (z < 0 || z > h) continue;
                    for (int d = 0; d < 3; d++) {
                        int nx = x + (d == 0), ny = y + (d == 1), nz = z + (d == 2);
                        if (nx > h || ny > h || nz > h) continue;
                        ll v = dp[x][y] + a[i][d];
                        if (v > nd[nx][ny]) nd[nx][ny] = v;
                    }
                }
            dp.swap(nd);
        }
        ll best = -1;
        for (int x = 0; x <= h; x++)
            for (int y = 0; y <= h; y++)
                if (dp[x][y] > best) best = dp[x][y];
        printf("%lld\n", best);
    }
    return 0;
}

2025 社团招新 · 方案一 状态计数DP

正文

CSP-S 标程 · 复赛真题的其它内容

2025 社团招新 · 方案一状态计数DP