uva 10817 - Headmaster's Headache ( 01背包状态压缩dp)

野性酷女 2021-12-15 19:47 223阅读 0赞

## 题意：有m个教师，n个求职者，需讲授s个课程，已知工资c和能教的课程集合，要求支付最少使每门课至少有两名教师，在职教师不能辞退。应该是保证有解的。（题目没说无解输出什么） ##

## 分析：枚举，两种情况，选和不选求职者。s0表示哪些科目没有一个老师教，s1表示是哪些科目只有一个老师教，s2表示有哪些科目有两个老师教，d(i,s1,s2)表示考虑钱i个时的最小花费，状态转移方程d(i,s1,s2)=min\{d(i+1,s1′,s2′)+c\[i\],d(i+1,s1,s2)\} 【c\[i\]表示聘用这个老师的花费,s1′和s2′表示招聘这个老师后更新的新状态′，第一项表示聘用，第二项不聘用，只有i>m才出现第二项，因为在职教师不能够辞退。状态转移有点复杂，位运算逻辑要理清楚。 ##

## 刘汝佳代码（记忆化搜索）： ##

#include<bits/stdc++.h>
    using namespace std;
    
    const int maxn = 100 + 20 + 5;
    const int maxs = 8;
    const int INF = 1000000000;
    int m, n, s, c[maxn], st[maxn], d[maxn][1<<maxs][1<<maxs];
    
    //s0是没有人能教的科目集合 s1是一个人教的科目集合，s2是两个人教的科目集合
    //s0二进制第i位为1表示第i个科目没有人能教，为0表示有人教
    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 >= 0) return ans;
        ans = INF;
        if(i >= m) ans = dp(i+1, s0, s1, s2); // 不选
        //i<m代表教师必须选（不能辞退） 
        int m0 = st[i] & s0, m1 = st[i] & s1;//st[i]表示第i个人能教的科目集合 
        //m0从s0晋级到s1,^是消除m0的意思
        s0 ^= m0;
        //m1是从s1晋级到s2的,消除s2,同时加上m0
        s1 = (s1 ^ m1) | m0;
        s2 |= m1;//加上m1
        ans = min(ans, c[i] + dp(i+1, s0, s1, s2));
        return ans;
    }
    
    int main()
    {
        int x;
        string line;
        while(getline(cin, line))
        {
            stringstream ss(line);
            ss >> s >> m >> n;
            if(s == 0) break;
            for(int i = 0; i < m+n; i++)
            {
                getline(cin, line);
                stringstream ss(line);
                ss >> c[i];
                st[i] = 0;
                while(ss >> x) st[i] |= (1 << (x-1));
            }
            memset(d, -1, sizeof(d));
            cout << dp(0, (1<<s)-1, 0, 0) << "\n";
        }
        return 0;
    }