题解 UVA10817 【Headmaster's Headache】

Prurite

2018-07-17 09:31:59

Solution

这一道题确实比较坑,让我 ~~在看了题解之后~~ 琢磨了很久,主要问题在于**细节**很多。 ## 题目大意 现在有一些在职教师和一些应聘的老师,每个老师需要一定的工资同时可以教一些科目,在职教师不能解雇,问使每个科目都至少有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)