andyli

题解 UVA10817 【校长的烦恼 Headmaster's Headache】
用两个集合,$s1$表示恰好有一个人教的科目集合,$s2$表示至少有两个人教的科目集合,而$d(i,s1,s2)$...
扫描右侧二维码阅读全文
29
2019/09

题解 UVA10817 【校长的烦恼 Headmaster's Headache】

用两个集合,$s1$表示恰好有一个人教的科目集合,$s2$表示至少有两个人教的科目集合,而$d(i,s1,s2)$表示已经考虑了前$i$个人时的最小花费。注意,把所有人一起从$0$编号,则编号$0\sim m-1$是在职教师,$m\sim n+m-1$是应聘者。状态转移方程为$d_{i,s1,s2}\min\{d_{i+1,s1',s2'}+c_i,d_{i+1,s1',s2'}\}$,其中第一项表示“聘用”,第二项表示“不聘用”。当$i\geq m$时状态转移方程才会出现第二项。这里$s1'$和$s2'$表示“招聘第$i$个人后$s1$和$s2$的新值”,具体计算方法见代码。
下面代码中的$st_i$表示第$i$个人能教的科目集合,$s0$表示没有任何人能教的科目集合。$s0$这个参数并不需要记忆,仅是为了编程的方便。
主要代码如下:

const int maxn = 130, maxs = 9, INF = -1u / 4; // -1u / 4 = 1073741823

int c[maxn], st[maxn], d[maxn][1 << maxs][1 << maxs], s, m, n;
int dp(int i, int s0, int s1, int s2)
{
    if (i == m + n)
        return s2 == (1 << s) - 1 ? 0 : INF;
    int& ans = d[i][s1][s2];
    if (~ans)
        return ans;
    ans = INF;
    if (i >= m)
        ans = dp(i + 1, s0, s1, s2); // 不选
    int m0 = st[i] & s0, m1 = st[i] & s1;
    return ans = min(ans, dp(i + 1, s0 ^ m0, (s1 ^ m1) | m0, s2 | m1) + c[i]); // 选
}
int main()
{
    while (io.read(s, m, n), s) {
        memset(d, -1, sizeof(d));
        memset(st, 0, sizeof(st));
        for (int i = 0; i < m + n; i++) {
            io.read(c[i]);
            char str[20];
            io.readline(str); // 读取这一行剩下的字符串
            stringstream ss;
            ss << str;
            int t;
            while (ss >> t)
                st[i] |= (1 << (t - 1)); // 科目以0开始编号
        }
        writeln(dp(0, (1 << s) - 1, 0, 0));
    }
    return 0;
}
Last modification:November 23rd, 2019 at 11:31 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment