Uva(10817)(Headmaster's Head

链接：https://vjudge.net/problem/UVA-10817
思路：有些日子没做dp了，上手做一个，一开始想的是用一个数来表示集合，后来发现拆为两个更方便一些，一个表示已经有一个老师的，一个表示有两个老师的，然后进行状态转移，对当前老师选或者不选，如果选的话更新集合状态，然后加上钱。本题坑点有点多，一个是输入，最好是用getline读入一行，然后用stringstream进行重定向。然后就是要注意位运算的优先级，以后所有位运算最好打上括号保证得到想要的顺序。
代码：

#include<bits/stdc++.h>
using namespace std;
int dp[1<<9][1<<9][130];
vector<int> T[130];
int money[130];
int s,m,n;

    int dfs(int i,int j,int k){
        if(dp[i][j][k]>=0)return dp[i][j][k];
        if(i==((1<<s)-1)&&(j==(1<<s)-1))return 0;
        if(k==m+n)return 1e9;
        int &res = dp[i][j][k];
            int ii = i;
            int jj = j;
//更新集合状态
            for(int p=0;p<T[k].size();p++){
                if((ii&(1<<T[k][p]))&&((jj&(1<<T[k][p]))==0))jj+=(1<<T[k][p]);//如果第一个已经有了老师，则更新第二个集合
                else if((ii&(1<<T[k][p]))==0)ii+=(1<<T[k][p]);//如果第一个没有则更新第一个
            }
            res=money[k] + dfs(ii,jj,k+1);
//不选当前老师
        int sum = dfs(i,j,k+1);

        res = min(res,sum);
        return res;
    }
    string line;
int main(){
    while(getline(cin,line)){
        stringstream ss(line);
        ss>>s>>m>>n;
        if(s==0)break;
        memset(dp,-1,sizeof(dp));
        for(int i=0;i<=m+n;i++)T[i].clear();
            int now1 = 0;
            int now2 = 0;
            int res = 0;
            int num;
        for(int i=0;i<m+n;i++){
            getline(cin,line);  
            stringstream ss(line);
            ss>>money[i]; 
            while(ss>>num){
                num--;
                T[i].push_back(num);
                if(i<m){
                    if(now1&(1<<num)&&((now2&(1<<num))==0))
                    now2+=(1<<(num));
                else if((now1&(1<<num))==0)
                    now1+=(1<<(num));
                }
            }
            if(i<m){
                res+=money[i];
            }
}
        int ans = res + dfs(now1,now2,m);
        cout<<ans<<endl;
    }
    return 0;
}