【YbtOJ#20077】计划带师

题目

题目链接：http://noip.ybtoj.com.cn/problem/20077

思路

设 (f[s]) 表示选了集合 (s) 里的作业做完，最小的代价。
由于最终方案要求字典序最小，所以我们要从后往前 dp，有转移

[f[s]=min_{i otin s(f[s])}(f[scup i]+max(t[scup i]-d[i],0)) ]

其中 (t[s]) 表示完成集合 (s) 里的作业需要的时间。
然后记录前驱输出即可。
时间复杂度 (O(T(2^n+2^{n-1}n)))。

代码

#include <bits/stdc++.h>
using namespace std;

const int N=55,M=(1<<20);
int Q,n,f[M],d[N],c[N],a[M],lg[M],pre[M];
char ch[N][N];

int main()
{
	freopen("work.in","r",stdin);
	freopen("work.out","w",stdout);
	for (int i=0;i<20;i++)
		lg[1<<i]=i;
	scanf("%d",&Q);
	while (Q--)
	{
		scanf("%d",&n);
		for (int i=0;i<n;i++)
			scanf("%s%d%d",&ch[i],&d[i],&c[i]);
		memset(f,0x3f3f3f3f,sizeof(f));
		f[(1<<n)-1]=0;
		for (int s=1;s<(1<<n);s++)
			a[s]=a[s-(s&-s)]+c[lg[s&-s]];
		for (int s=(1<<n)-1;s;s--)
			for (int i=s;i;i-=i&-i)
				if (f[s^(i&-i)]>=f[s]+max(a[s]-d[lg[i&-i]],0))
				{
					f[s^(i&-i)]=f[s]+max(a[s]-d[lg[i&-i]],0);
					pre[s^(i&-i)]=(i&-i);
				}
		printf("%d
",f[0]);
		for (int s=0;s!=(1<<n)-1;s^=pre[s])
			printf("%s
",ch[lg[pre[s]]]);
	}
	return 0;
}