题意：
有S个课程要教，
学校本来有m个教师 给出工资和所教课程编号（在职教师不能辞退）
来应聘的有n个教师 给出工资和所教课程编号
问保证每个课程都有两个老师可以教的前提下，最少发多少工资
思路：
水题；
总共最多只有8个课程，，状态压缩
d[i][s1][s2] 表示当前状态下，有一个老师教的课程是s1，有两个或两个人以上教的课程是s2
转移就是当前教师选或不选，对应的转移到下一个（i+1个）教师的决策即可。
code：
#include<cstdio>#include<iostream>#include<sstream>#include<cstring>#include<algorithm>#include<vector>#include<string>#include<queue>#include<map>#include<set>#include<cmath>#include<cctype>#include<cstdlib>using namespace std;#define INF 0x3f3f3f3f#define PI acos(-1.0)#define mem(a, b) memset(a, b, sizeof(a))#define mod 1000000007typedef pair<int,int> pii;typedef long long LL;//——————————const int maxn = 125;const int maxs = (1<<8);int S,m,n;int cost[maxn], s[maxn];void init(){string line;int tmp;for(int i = 0; i < m+n; i++){getline(cin, line);stringstream ss(line);ss >> cost[i];s[i] = 0;while(ss >> tmp) s[i] |= (1 << (tmp-1));}}int d[maxn][maxs][maxs];int dfs(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 = dfs(i+1, s0, s1, s2);int m0 = s[i] & s0, m1 = s[i] & s1;s0 ^= m0;s1 = (s1 ^ m1) | m0;s2 |= m1;ans = min(ans, cost[i] + dfs(i+1, s0, s1, s2));return ans;}void solve(){memset(d, -1, sizeof(d));int ans = dfs(0,(1<<S)-1, 0,0);printf("%d\n",ans);}int main(){while(scanf("%d%d%d",&S, &m, &n) != EOF){getchar();if(S == 0) break;init();solve();}return 0;}一开始没有用
getlin(cin, line);
stringstream ss(line);
ss >> cost[i];
while(ss>>tmp){
}
这种方式来处理，而是采取了读入到换行符的方式；
现在通过这道题目学习了一种新的处理方式。很好
code2：
#include<cstdio>#include<iostream>#include<sstream>#include<cstring>#include<algorithm>#include<vector>#include<string>#include<queue>#include<map>#include<set>#include<cmath>#include<cctype>#include<cstdlib>using namespace std;#define INF 0x3f3f3f3f#define PI acos(-1.0)#define mem(a, b) memset(a, b, sizeof(a))#define mod 1000000007typedef pair<int,int> pii;typedef long long LL;//——————————const int maxn = 125;const int maxs = (1<<8);int S,m,n;int cost[maxn], s[maxn];void init(){int tmp;char ch;for(int i = 0; i < m+n; i++){scanf("%d",&tmp);cost[i] = tmp;s[i] = 0;while(1){scanf("%c",&ch);if(ch == '\n') break;if(isdigit(ch)){tmp = ch – '0';s[i] |= (1<<(tmp-1));}}}}int d[maxn][maxs][maxs];int dfs(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 = dfs(i+1, s0, s1, s2);int m0 = s[i] & s0, m1 = s[i] & s1;s0 ^= m0;s1 = (s1 ^ m1) | m0;s2 |= m1;ans = min(ans, cost[i] + dfs(i+1, s0, s1, s2));return ans;}void solve(){memset(d, -1, sizeof(d));int ans = dfs(0,(1<<S)-1, 0,0);printf("%d\n",ans);}int main(){while(scanf("%d%d%d",&S, &m, &n) != EOF){getchar();if(S == 0) break;init();solve();}return 0;}maxs定义太大会超时
你说只有有缘人才可以取下，我看着你手中的戒指，想做你的有缘人，
