Doing Homework HDU

题意：

有n个作业，每个作业有一个截止时间和完成所需时间，如果完成某个作业的时间超出了截止时间就扣完成时间-截止时间的分。求按怎样的顺序完成作业扣分最少。

方法：状压dp。ans[S]表示完成集合S的作业最少的扣分（集合S用一个数字表示）。pre[S]和pre2[S]分别表示由前一个状态到达状态S完成的作业序号、S的前一个状态。

首先应该意识到完成某个集合的作业，不管按照何顺序，总时间都是一样的。（曾经没发现导致没思路）

从小到大枚举S（这样的话枚举到每个集合时其去掉某个作业得到的集合保证都已经枚举到过，因为其子集的数字表示一定小于S）。

$ans[S]=min{ans[S-p]+max(sumt[S]-d[p],0)}$（p表示S集合内任意一项作业）

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<vector>
 5 using namespace std;
 6 typedef long long LL;
 7 char name[16][110];
 8 LL d[16],c[16],ans[70000];
 9 LL pre[70000],pre2[70000];
10 LL T,n,sumt;
11 vector<LL> vec;
12 int main()
13 {
14     LL i,j,t;
15     scanf("%lld",&T);
16     while(T--)
17     {
18         memset(name,0,sizeof(name));
19         memset(ans,0x3f,sizeof(ans));
20         memset(pre,0,sizeof(pre));
21         memset(pre2,0,sizeof(pre2));
22         scanf("%lld",&n);
23         for(i=1;i<=n;i++)
24             scanf("%s%lld%lld",name[i],&d[i],&c[i]);
25         ans[0]=0;
26         for(i=1;i<(1<<n);i++)
27         {
28             sumt=0;
29             for(j=1;j<=n;j++)
30                 if(i&(1<<(j-1)))
31                     sumt+=c[j];
32             for(j=1;j<=n;j++)
33                 if(i&(1<<(j-1)))
34                 {
35                     t=ans[i^(1<<(j-1))]+max(sumt-d[j],0LL);
36                     if(t<=ans[i])
37                     {
38                         ans[i]=t;
39                         pre[i]=j;
40                         pre2[i]=i^(1<<(j-1));
41                     }
42                 }
43         }
44         printf("%lld
",ans[(1<<n)-1]);
45         vec.clear();
46         for(i=(1<<n)-1;i!=0;i=pre2[i])
47             vec.push_back(pre[i]);
48         for(i=vec.size()-1;i>=0;i--)
49             printf("%s
",name[vec[i]]);
50     }
51     return 0;
52 }

某题解

一个裸状态压缩~

题目大意: 一共有N门作业,三个数据是作业的名字,到期时间,和完成需要天数,完成做也期限超过一天扣一分.问以什么顺序完成作业可以使扣得分最少.如果有相同的分数名字按字典序排序.

状态转移方程: dp[i]=min(dp[j]+hw[k]-hwlast[k])+hw[k]; j为i中去掉第k个作业的状态,hw[k]为当前作业需要几天完成,hwlast为当前作业完成期限为多少,若(dp[j]+hw[k]<hwlast[k])则取零,表示状态不可用.

源代码:

#include <myhead.h>

const int N=16;
const int M=110;
const int NUM=(1<<N);
struct HomeWork {
	char name[M];
	int last;
	int time;
};
struct Dp {
	int timer;
	int scr;
	int last;
	int i;
	void init() {
		this->timer=0;
		this->scr=INT_MAX;
		this->last=0;
		this->i=0;
	}
};
int n,num;
HomeWork hw[N];
Dp dp[NUM];

void init() {
	scanf("%d",&n);
	num=(1<<n);
	dp[0].init();
	dp[0].scr=0;
	for(int i=0;i<n;++i) {
		scanf("%s%d%d",hw[i].name,&hw[i].last,&hw[i].time);
	}
}

void work() {
	for(int i=1;i<num;++i) {
		dp[i].init();
		for(int j=n-1;j>=0;--j) {
			int s=(1<<j);
			if(s&i) {
				int past=i-s;
				int t=dp[past].timer+hw[j].time-hw[j].last;
				checkmax(t,0);
				t+=dp[past].scr;
				if(t<dp[i].scr) {
					dp[i].scr=t;
					dp[i].i=j;
					dp[i].last=past;
					dp[i].timer=dp[past].timer+hw[j].time;
				}
			}
		}
	}
	stack<int> s;
	int star=num-1;
	while(star) {
		s.push(dp[star].i);
		star=dp[star].last;
	}
	printf("%d
",dp[num-1].scr);
	while(!s.empty()) {
		printf("%s
",hw[s.top()].name);
		s.pop();
	}
}

int main() {
	int t;
	scanf("%d",&t);
	while(t--) {
		init();
		work();
	}
	return 0;
}