欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

*HDU1074.Doing Homework(状压DP)

程序员文章站 2022-06-16 19:48:45
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1074题意:给出n个课程,每个课程给出课程名称、截止日期、完成需要的时间,超过截止日期完成的课程每超过一天减少分数1。求最少减少的分数方案,如果有多个方案,输出字典序最小的方案解题思路:因为n最大是15,可以使用二进制来进行状压DP讨论。dp结构体:struct plan{int pre; //记载上一个状态int choice; //记录当前状态选择的课程int time;...

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1074
题意:给出n个课程,每个课程给出课程名称、截止日期、完成需要的时间,超过截止日期完成的课程每超过一天减少分数1。求最少减少的分数方案,如果有多个方案,输出字典序最小的方案
解题思路:因为n最大是15,可以使用二进制来进行状压DP讨论。
dp结构体:

struct plan{
	int pre;     //记载上一个状态
	int choice;  //记录当前状态选择的课程
	int time;    //记录当前课程完成需要的时间
	int score;   //记录减少的得分
}dp[(1<<15)+10];

dp主体部分:

for(int i=1;i<=end;i++){
			dp[i].score=99999999;
			for(int j=n-1;j>=0;j--){   //从后往前遍历
				int tmp=1<<j;
				if(i&tmp){
					int ttmp=i-tmp;
					 //计算超时多少
					int tmp_cost=dp[ttmp].time+hw[j].c-hw[j].d;  
					//如果超时不为正数,则扣分为0
					if(tmp_cost<0) tmp_cost=0;
					if(tmp_cost+dp[ttmp].score<dp[i].score){
						dp[i].score=tmp_cost+dp[ttmp].score;
						dp[i].time=dp[ttmp].time+hw[j].c;
						dp[i].pre=ttmp;
						dp[i].choice=j;
					}
				}
			}
		}

递归输出:

void print(int pos){
	if(pos==0)
		return ;
	print(dp[pos].pre);
	cout<<hw[dp[pos].choice].name<<endl;
	return ;
}
#include<cstdio>
#include<iostream>
#include<string>
#include<string.h>
using namespace std;
int t;
int n;
struct node{
	string name;
	int d,c;
}hw[30];
struct plan{
	int pre;
	int choice;
	int time;
	int score;
}dp[(1<<15)+10];
void print(int pos){
	if(pos==0)
		return ;
	print(dp[pos].pre);
	cout<<hw[dp[pos].choice].name<<endl;
	return ;
}
int main(){
	cin>>t;
	while(t--){
		memset(dp,0,sizeof(dp));
		cin>>n;
		for(int i=0;i<n;i++){
			cin>>hw[i].name;
			cin>>hw[i].d>>hw[i].c;
		}
		int end=(1<<n)-1;
		for(int i=1;i<=end;i++){
			dp[i].score=99999999;
			for(int j=n-1;j>=0;j--){
				int tmp=1<<j;
				if(i&tmp){
					int ttmp=i-tmp;
					int tmp_cost=dp[ttmp].time+hw[j].c-hw[j].d;
					if(tmp_cost<0) tmp_cost=0;
					if(tmp_cost+dp[ttmp].score<dp[i].score){
						dp[i].score=tmp_cost+dp[ttmp].score;
						dp[i].time=dp[ttmp].time+hw[j].c;
						dp[i].pre=ttmp;
						dp[i].choice=j;
					}
				}
			}
		}
		cout<<dp[end].score<<endl;
		print(end);
	}
	return 0;
}

本文地址:https://blog.csdn.net/littlegoldgold/article/details/107297188