HDU1074 Doing Homework

题目描述

题目共有 T 组测试, 每组测试给定 n 个作业, 每个作业有 完成需要的时间 和 截止日期, 所有作业都需要完成, 每超过截止日期一天就会扣一分, 问最少扣分以及完成次序.

解题思路

第一次做 状态压缩DP 的题, 题目的解的值和不同科目的次序相关, 如果需要穷举次序的话共有 N! (n属于[1, 15]) 种方案

可以使用 n 位的二进制来表示 n 种方案是否完成, 如果有 A, B, C 三个作业, 可以使用 001 表示只有 A 完成. 对于 ABC 之后的 D 来讲, ABC完成次序与到达 D 的时间花费无关, ABC 的不同排列会使到达 D 的扣的分数不同, 而在 D 时只需要选择分数被扣最小的方案即可.

对于每个状态, 如 001110, 可以从三个状态 001100, 001010, 000110 转移得到, 因此需要 枚举每一位 , 看这一位是否为 该状态的前置状态 , 是的话, 则通过计算 前面状态的最小花费 加 被枚举事件的所扣分数 来更新该状态被扣分数的最小值.

由于当前枚举的为现在做的作业, 即在前面作业完成后完成的, 因此需要从大数开始枚举, 前面的小数在 i 的循环时已经得到了相应的状态.

代码

package 基础DP1;

import java.util.Scanner;
import java.util.Stack;
class Homework {
	public String name;
	public int deadline;
	public int cost;
	public Homework(String name, int deadline, int cost) {
		super();
		this.name = name;
		this.deadline = deadline;
		this.cost = cost;
	}
	
}
class Node {
	public int nowtime;
	public int score;
	public int num;
	public int pre;
}
public class HDU1074 {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int nCase = in.nextInt();
		while(0 != nCase--) {
			int nSubject = in.nextInt();
			Homework[] h = new Homework[nSubject];
			for(int i = 0; i < nSubject; i++) {
				String name = in.next();
				int deadline = in.nextInt();
				int cost = in.nextInt();
				h[i] = new Homework(name, deadline, cost);
			}
			int nSta = (1 << nSubject) - 1;
			Node[] dp = new Node[nSta + 1];
			for(int i = 0; i <= nSta; i++)
				dp[i] = new Node();
			for(int i = 1; i <= nSta; i++) {
				dp[i].score = Integer.MAX_VALUE;
				for(int j = nSubject - 1; j >= 0; j--) {
					int temp = 1 << j;
					if((temp & i) != temp)
						continue;
					int k = i - temp;
					int x = dp[k].nowtime + h[j].cost - h[j].deadline;
					if(x < 0) 
						x = 0;
					if(dp[k].score + x < dp[i].score) {
						dp[i].score = dp[k].score + x;
						dp[i].nowtime = dp[k].nowtime + h[j].cost;
						dp[i].num = j;
						dp[i].pre = k;
					}
				}
			}
			System.out.println(dp[nSta].score);
			Stack<Integer> st = new Stack<Integer>();
			while(nSta != 0) {
				st.push(dp[nSta].num);
				nSta = dp[nSta].pre;
			}
			while(!st.isEmpty()) {
				System.out.println(h[st.peek()].name);
				st.pop();
			}
		}
		in.close();
	}
}

参考链接

HDU 1074：Doing HomeWork(状态压缩DP)

[HDU 1074 (状态压缩DP)](http://www.cnblogs.com/neopenx/p/4048722.html)