首页 > 代码库 > HDU - 1074 Doing Homework

HDU - 1074 Doing Homework

题意:学生有多个任务,每个任务有规定完成的时间,还有完成的时间,超过规定一天就扣一分,求最少的扣分,相同的话,按字典序

思路:DP的状态搜索,每次枚举一个,然后从第一个开始匹配,因为题目已经排序了,所以不用考虑这个字典序最小了,对于每次新加进来的,如果超过规定时间就计算多出来的,没有的话,就是0了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 20;
const int INF = 0x3f3f3f3f;

struct Node {
	char name[200];
	int D,C;
}node[MAXN];
int dp[1<<MAXN];
int pre[1<<MAXN];
int n;

void print(int s) {
	if (s == 0)
		return;
	int cnt = 0;
	for (int i = 0; i < n; i++) 
		if ((s&(1<<i)) != 0 && (pre[s]&(1<<i)) == 0) {
			cnt = i;
			break;
		}
	print(pre[s]);
	printf("%s\n", node[cnt].name);
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d%*c", &n);
		for (int i = 0; i < n; i++)
			scanf("%s%d%d", node[i].name, &node[i].D, &node[i].C);
		for (int i = 0; i < (1<<n); i++)
			dp[i] = INF;
		dp[0] = 0;
		for (int i = 0; i < (1<<n); i++) {
			for (int j = 0; j < n; j++) {
				if (i & (1<<j))	
					continue;
				int cnt = 0;
				for (int k = 0; k < n; k++) 
					if (i & (1<<k))
						cnt += node[k].C;
				cnt += node[j].C;
				if (cnt > node[j].D)
					cnt -= node[j].D;
				else cnt = 0;
				if (dp[i|(1<<j)] > dp[i]+cnt) {
					dp[i|(1<<j)] = dp[i]+cnt;
					pre[i|(1<<j)] = i;
				}
			}
		}
		printf("%d\n", dp[(1<<n)-1]);
		print((1<<n)-1);
	}
	return 0;
}