题解 P3212 【[HNOI2011]任务调度】

· · 题解

一个RP完全问题

当成dp想不出来，然后发现标签随机化233

枚举第三种任务先在A还是先在B，再随便贪心一下任务1，2的顺序，然后就是大力随机交换A，B机器任务执行的先后顺序，贪心计算时间，如果更优就保存，大概每次随机2000组够了

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 30;
const int inf = INT_MAX / 3;
int n, a[MAX_N], b[MAX_N], t[MAX_N], ans = inf;
int que_a[MAX_N], que_b[MAX_N], top_a, top_b;
bool flag[MAX_N];
int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
    while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
bool cmp_a(int x, int y)
{
    return b[x] == b[y] ? a[x] < a[y] : b[x] > b[y];
}
bool cmp_b(int x, int y)
{
    return a[x] == a[y] ? b[x] < b[y] : a[x] > a[y];
}
int calc()
{
    int sum_a = 0, sum_b = 0, re = 0;
    for (int i = 1; i <= top_a; i++)
        sum_a += a[que_a[i]];
    for (int i = 1; i <= top_b; i++)
    {
        sum_b += b[que_b[i]];
        if (sum_a > sum_b) sum_a += a[que_b[i]];
        else sum_a = sum_b + a[que_b[i]];
    }
    re = max(sum_a, sum_b);
    sum_a = sum_b = 0;
    for (int i = 1; i <= top_b; i++)
        sum_b += b[que_b[i]];
    for (int i = 1; i <= top_a; i++)
    {
        sum_a += a[que_a[i]];
        if (sum_b > sum_a) sum_b += b[que_a[i]];
        else sum_b = sum_a + b[que_a[i]];
    }
    return max(re, max(sum_a, sum_b));
}
void solve()
{
    top_a = top_b = 0;
    for (int i = 1; i <= n; i++)
        if (flag[i]) que_b[++top_b] = i;
        else que_a[++top_a] = i;
    sort(que_a + 1, que_a + top_a + 1, cmp_a);
    sort(que_b + 1, que_b + top_b + 1, cmp_b);
    int re = calc();
    for (int cas = 1; cas <= 2000; cas++)
    {
        int a1, a2, b1, b2, tmp;
        if (top_a)
            swap(que_a[a1 = (rand() % top_a) + 1], que_a[a2 = (rand() % top_a) + 1]);
        if (top_b)
            swap(que_b[b1 = (rand() % top_b) + 1], que_b[b2 = (rand() % top_b) + 1]);
        tmp = calc();
        if (tmp < re) re = tmp;
        else
        {
            if (top_a) swap(que_a[a1], que_a[a2]);
            if (top_b) swap(que_b[b1], que_b[b2]);
        }
    }
    if (re < ans) ans = re;
}
void dfs(int dep)
{
    if (dep > n) solve();
    else if (t[dep] == 1) flag[dep] = 0, dfs(dep + 1);
    else if (t[dep] == 2) flag[dep] = 1, dfs(dep + 1);
    else
    {
        flag[dep] = 0; dfs(dep + 1);
        flag[dep] = 1; dfs(dep + 1);
    }
}
int main()
{
    srand(time(NULL) + 19260817);
    n = read();
    for (int i = 1; i <= n; i++)
        t[i] = read(), a[i] = read(), b[i] = read();
    dfs(1);
    printf("%d\n", ans);
    return 0;
}