传送!
某校有(m)个教师和(n)个求职者，需讲授(s)个课程。已知每人的工资(c)和能教的课程集合，要求支付最少的工资使得每门课都至少有两名教师能教。在职教师不能辞退。（数据范围见原题面）
因为课程很少，直接状压dp。
状压的时候有两种思路：一是三进制状态压缩，二是开两个(2^8)的状态分别表示这么课有1/2个老师教。
初始状态是(m)个教师教课时的状态。
转移的时候，对于每一个求职者，枚举当时所有的教课状态，转移到让这个求职者教课后的状态即可。
三进制状态压缩不是很好写，而且要保证当这门课有大于两个老师的时候也按两个老师来算，所以就一位一位考虑好了。
时间复杂度(O(n * 3 ^ s * s))。
不过最坑爹的还是读入，不告你每一个老师教几个课程，我直接暴力getchar加循环判断了。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<queue>
#include<assert.h>
#include<ctime>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
#define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt)
typedef long long ll;
typedef double db;
const int INF = 2147483647;
const db eps = 1e-8;
const int maxn = 125;
const int maxs = 7e3 + 5;
const int N = 8;
const int NUM = 6561;
In ll read()
{
ll ans = 0;
char ch = getchar(), las = ' ';
while(!isdigit(ch)) las = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(las == '-') ans = -ans;
if(ch == '
' || las == '
') return -1;
return ans;
}
In void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
In void MYFILE()
{
#ifndef mrclr
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
}
int n, m, S;
int a[maxn], sub[maxn];
int p[N + 2];
In void input() //坑爹的读入
{
for(int i = 1; i <= n + m; ++i)
{
while(1)
{
int ans = 0;
char ch = getchar();
while(!isdigit(ch))ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
ans > N ? a[i] = ans : sub[i] += p[ans - 1];
if(ch == '
') break;
}
}
}
int s[maxs][N + 2];
int dp[maxn][maxs], MAX;
In void solve()
{
int beg = 0; //构造初始状态
for(int i = 1; i <= m; ++i)
{
int tp = 0;
for(int j = 0; j < N; ++j) tp += p[j] * min(2, s[beg][j] + s[sub[i]][j]);
dp[i][tp] = dp[i - 1][beg] + a[i];
beg = tp;
}
for(int i = m + 1; i <= n + m; ++i)
{
for(int j = beg; j <= MAX; ++j) dp[i][j] = dp[i - 1][j];
for(int j = beg; j <= MAX; ++j)
if(dp[i - 1][j] != INF)
{
int tp = 0;
for(int k = 0; k < N; ++k) tp += p[k] * min(2, s[j][k] + s[sub[i]][k]);
dp[i][tp] = min(dp[i][tp], dp[i - 1][j] + a[i]);
}
}
}
In void init()
{
for(int i = 1; i <= n; ++i)
for(int j = 0; j <= NUM; ++j) dp[i][j] = INF;
dp[0][0] = 0;
Mem(sub, 0);
MAX = pow(3, S) - 1;
}
In void calc(int x)
{
for(int i = 0, j = x; j; ++i, j /= 3) s[x][i] = j % 3;
}
int main()
{
// MYFILE();
for(int i = 0; i <= NUM; ++i) calc(i); //预处理每一个数的三进制
p[0] = 1;
for(int i = 1; i < N; ++i) p[i] = p[i - 1] * 3;
while(scanf("%d%d%d", &S, &m, &n) && S)
{
init(), input();
solve();
write(dp[n + m][MAX]), enter;
}
return 0;
}