题解 UVA10817 【Headmaster's Headache】
Prurite
2018-07-17 09:31:59
这一道题确实比较坑,让我 ~~在看了题解之后~~ 琢磨了很久,主要问题在于**细节**很多。
## 题目大意
现在有一些在职教师和一些应聘的老师,每个老师需要一定的工资同时可以教一些科目,在职教师不能解雇,问使每个科目都至少有2位老师教的最小总工资支出。
## 分析与解
### 状压DP
因为此题数据范围很小(只有不超过8个科目),并且每个科目又有多个状态(没人教,1人教,2人教),我们就可以想到用状态压缩的思想进行解题。本题是可以使用3进制状压的,但是为方便我就使用4进制了(用两个2进制位表示一个状态)。
我们设 00,01,11 分别表示一个科目有0人,1人,1人以上时的情况,容易想出先算出所有在职老师可以教的科目情况,再逐个枚举应聘老师进行转移。
令 `dp[i][m]` 表示当前考虑到第 $i$ 个应聘老师,各科目状态为 $m$ 时的最小花费,则
```
dp[i][m]=min( dp[i-1][m], dp[i-1][temp]+c[i] )
```
(其中temp为假设没有该老师时的状态)。
初始化及边界:先全部置为 INF ,然后
```
dp[0][当前在职老师能教的状态]=在职老师的工资和
```
听上去这题就做完了,对吧。
但是这里有一个大坑:试试这组数据
```
2 2 2
10000 1
10000 1
10000 1 2
10000 2
```
如果这么做程序会输出 INF 。
因为题目只要求“每科目有至少2个老师”,换而言之,新聘来的老师的科目与原来已经有2个及以上老师教的科目重复也是可以的。所以,我们还需要把所有“在职教师能教的状态的子状态”的花费也置为原来的花费,即,如果某一科目原来就有2人教了,我们还需要把描述这一科目只有1人教、没人教的状态进行初始化。
此题还有很多细节,具体的实现可以看代码。
注意灵活运用位运算。
## 代码
并不是很优秀,大家凑合着看吧。
```cpp
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN=100+1, MAXS=16, INF=0x3f3f3f3f;
int c[MAXN], a[MAXN];
// a[i]表示第i位老师能教的科目,c[i]表示第i位老师的工资
int dp[MAXN][1<<MAXS];
int s, p1, p2, k1, c1;
inline int min( int a, int b )
{
return a<b?a:b;
}
inline void read( );
inline int solve( );
int main( )
{
while ( ~scanf( "%d %d %d", &s, &p1, &p2 ) && s!=0 )
{
read( );
int ans=solve( );
printf( "%d\n", ans );
}
return 0;
}
inline void read( )
{
memset( a, 0, sizeof a );
memset( c, 0, sizeof c );
k1=c1=0;
// k1表示原在职老师的授课情况,c1表示原总工资
for ( int i=1; i<=p1; i++ )
{
int c2;
scanf( "%d", &c2 );
c1+=c2;
int k2=0;
while ( getchar( )!='\n' )
{
scanf( "%d", &k2 );
if ( (k1>>2*(k2-1)&3) == 1 )
k1|=1<<2*k2-1; // 由01改为11
else if ( (k1>>2*(k2-1)&3) == 0 )
k1|=1<<2*(k2-1); // 由00改为01
}
} // 处理在职老师
for ( int i=1; i<=p2; i++ )
{
scanf( "%d", &c[i] );
int k2;
while ( getchar( )!='\n' )
{
scanf( "%d", &k2 );
a[i]|=1<<2*(k2-1);
}
} // 读入新老师
return;
}
inline int solve( )
{
memset( dp, INF, sizeof dp ); // 初始化为INF
for ( int m=0; m<1<<2*s; m++ )
{
bool ok=1;
for ( int i=1; i<=s; i++ )
{
int x=m>>2*(i-1)&3, y=k1>>2*(i-1)&3;
if ( x==2 ) ok=0;
if ( x>y ) ok=0;
}
if ( ok )
dp[0][m]=c1;
} // 将所有“子状态”的花费设为c1
for ( int i=1; i<=p2; i++ )
for ( int m=0; m<1<<2*s; m++ )
{
int m1=m;
dp[i][m]=dp[i-1][m];
bool ok=1;
for ( int j=1; j<=s; j++ )
if ( a[i]&1<<2*(j-1) && ( m&1<<2*(j-1) || m&1<<2*j-1 ) )
{
if ( (m>>2*(j-1)&3) == 3 )
m1^=1<<2*j-1;
else if ( (m>>2*(j-1)&3) == 1 )
m1^=1<<2*(j-1);
else if ( (m>>2*(j-1)&3) == 0 )
{
ok=0;
break;
}
}
// 获得“如果当前老师不教”时的状态
if ( !ok )
continue;
dp[i][m]=min( dp[i][m], dp[i-1][m1]+c[i] );
}
return dp[p2][(1<<2*s)-1];
}
```
[提交记录](https://www.luogu.org/record/show?rid=8546536)