UVA10817--状态压缩DP

第一次做状态压缩dp。。没有思路。。看书看明白的，不过看完发现汝哥的做法多算了一些东西，完全可以省去不算。。

用两个集合，s1表示恰好有一个人教的科目，s2表示至少有两个人教的科目。d(i,s1,s2),表示考虑了前i个人时的最小花费，0-m-1必须全选上，m到m-n-1才有可能出现选或者不选的

决策，状态转移方程：d(i，s1，s2)=min{d(i+1,s1，s2)，fee[i] + d(i+1，s1‘，s2’)},第一项表示不聘用，还是以现在的s1，s2进入第i+1个人，第二项表示聘用，并且更新状态。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<cmath>
#include<sstream>
#include<queue>
#define INF 1000000000
using namespace std;
const int maxn = 205;

int s,m,n;
int fee[200];
int st[200];
int d[150][1<<8][1<<8];

int dp(int i, int s1, int s2) {//学习啦。。。orz
  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, s1, s2);

  int m1 = st[i] & s1;
  s1 = st[i]^s1;
  s2 |= m1;
  ans = min(ans, fee[i] + dp(i+1, s1, s2));//orz。。
  return ans;
}

int main()
{
    //freopen("in","r",stdin);
    string line;
    while(getline(cin,line))//学习一下读入方式orz
    {
        stringstream ss(line);
        ss>>s>>m>>n;
        if(s == 0) break;
       // cout<<s<<m<<n;
        for(int i = 0; i < m+n; ++i)
        {
            getline(cin,line);
            stringstream ss(line);
            ss >> fee[i];//printf("***%d
",fee[i]);
            int x;
            st[i] = 0;
            while(ss >> x) st[i]|=(1<<(x-1));//ss有个返回值？
        }
        memset(d,-1,sizeof(d));//注意初始化！！
        cout<<dp(0,0,0)<<endl;//初始状态，从第0个人，s1 = 0，s2 = 0；
    }
}