首页 > ACM题库 > HDU-杭电 > HDU 1074 Doing Homework-动态规划-[解题报告] C++
2013
11-27

HDU 1074 Doing Homework-动态规划-[解题报告] C++

Doing Homework

问题描述 :

Ignatius has just come back school from the 30th ACM/ICPC. Now he has a lot of homework to do. Every teacher gives him a deadline of handing in the homework. If Ignatius hands in the homework after the deadline, the teacher will reduce his score of the final test, 1 day for 1 point. And as you know, doing homework always takes a long time. So Ignatius wants you to help him to arrange the order of doing homework to minimize the reduced score.

输入:

The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case start with a positive integer N(1<=N<=15) which indicate the number of homework. Then N lines follow. Each line contains a string S(the subject’s name, each string will at most has 100 characters) and two integers D(the deadline of the subject), C(how many days will it take Ignatius to finish this subject’s homework).

Note: All the subject names are given in the alphabet increasing order. So you may process the problem much easier.

输出:

For each test case, you should output the smallest total reduced score, then give out the order of the subjects, one subject in a line. If there are more than one orders, you should output the alphabet smallest one.

样例输入:

2
3
Computer 3 3
English 20 1
Math 3 2
3
Computer 3 3
English 6 3
Math 6 3

样例输出:

2
Computer
Math
English
3
Computer
English
Math

Hint
In the second test case, both Computer->English->Math and Computer->Math->English leads to reduce 3 points, but the word "English" appears earlier than the word "Math", so we choose the first order. That is so-called alphabet order.

http://acm.hdu.edu.cn/showproblem.php?pid=1074

动态压缩dp,感觉还是没有怎么懂,主要用的是二进制的位运算。有待于研究。

//动态压缩dp
#include <stdio.h>
#include <iostream>
#include <cstring>

using namespace std;

typedef struct _homework
{
	char name[102];
	int deadline;
	int needday;
}homework;

homework hwk[16];
int n;

typedef struct _DP
{
	int ndday;
	int pre;
	int lowcost;
}DP;

DP dp[1<<15];
bool visited[1<<15];

void output(int status)
{
	int curwk = dp[status].pre ^ status;
	int curid = 0;
	curwk >>= 1;
	while(curwk){
		curid ++;
		curwk >>= 1;
	}
	if(dp[status].pre != 0){
		output(dp[status].pre);
	}
	printf("%s\n", hwk[curid].name);
}

int main()
{
	freopen("input.txt", "r", stdin);
	int t, i, j;
	int upper, cur, curtmp, reduce;
	scanf("%d", &t);
	while(t --){
		scanf("%d", &n);
		for(i = 0; i < n; i ++){
			scanf("%s%d%d", hwk[i].name, &hwk[i].deadline, &hwk[i].needday);
		}
		memset(visited, false, sizeof(visited));
		upper = (1 << n) - 1;//最大
		dp[0].ndday = 0, dp[0].lowcost = 0, dp[0].pre = -1;
		visited[0] = true;
		for(i = 0; i < upper; i ++){
			for(j = 0; j < n; j ++){
				cur = 1 << j;
				if((cur & i) == 0){
					curtmp = cur | i;
					dp[curtmp].lowcost = dp[i].lowcost + hwk[j].needday;
					reduce = dp[curtmp].lowcost - hwk[j].deadline;
					if(reduce < 0)reduce = 0;
					reduce += dp[i].ndday;
					if(visited[curtmp]){
						if(reduce < dp[curtmp].ndday){
							dp[curtmp].ndday = reduce;
							dp[curtmp].pre = i;
						}
					}
					else {
						visited[curtmp] = true;
						dp[curtmp].ndday = reduce;
						dp[curtmp].pre = i;
					}//else
				}//if
			}//for
		}//for
		printf("%d\n", dp[upper].ndday);
		output(upper);
	}//while
	return 0;
}


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  3. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }