HDU-1074 Doing Homework 状态压缩DP

本文主要是介绍HDU-1074 Doing Homework 状态压缩DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

题目大意： 有n个作业，每个作业有各自的完成期限与完成所需时间。每个作业每超过完成期限一个单位时间扣1学分，问怎么安排完成作业顺序使得所扣学分最少。

由于n小于等于15 状态少 明显可以用二进制压缩状态枚举排列 要注意的 答案相同要按作业名字典序排。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include<functional>
#include <queue>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
const int maxn = 16;
const int inf = 1<<30;
typedef __int64 LL;
int n;
struct node
{string name;int dl,cost;
}sub[maxn];
struct Node
{int Time,score,pre;
}dp[1<<maxn];
void GetDp()
{int tmp,pre;dp[0].score = 0; dp[0].Time = 0; dp[0].pre = -1;for( int s = 1; s < (1<<n); s ++ ){dp[s].score = inf;for( int i = 0; i < n; i ++ ){if( s&(1<<i) ){pre = s-(1<<i);tmp = dp[pre].Time + sub[i].cost - sub[i].dl;if( tmp < 0 )	tmp = 0;if( dp[pre].score + tmp <  dp[s].score ){dp[s].score = dp[pre].score + tmp;dp[s].Time = dp[pre].Time + sub[i].cost;dp[s].pre = i;}else if( dp[pre].score + tmp ==  dp[s].score && sub[i].name > sub[dp[s].pre].name ){dp[s].pre = i;}}}}
}
void Outup( int s )
{if( s == 0 )	return;int preS = s - (1<<dp[s].pre);Outup( preS );cout<<sub[dp[s].pre].name<<endl;
}
int main()
{#ifndef ONLINE_JUDGE  freopen("data.txt","r",stdin);  #endif  int cas;scanf("%d",&cas);while( cas -- ){scanf("%d",&n);for( int i = 0; i < n; i ++ )cin>>sub[i].name>>sub[i].dl>>sub[i].cost;GetDp();printf("%d\n",dp[(1<<n)-1].score);Outup( (1<<n)-1 );}return 0;
}

#include <stdio.h>
#include <string.h>
#include <iostream>
#include<functional>
#include <queue>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
const int maxn = 16;
const int inf = 1<<30;
typedef __int64 LL;
int n;
struct node
{string name;int dl,cost;
}sub[maxn];
struct Node
{int Time,score,pre;
}dp[1<<maxn];
void GetDp()
{int tmp,pre;dp[0].score = 0; dp[0].Time = 0; dp[0].pre = -1;for( int s = 1; s < (1<<n); s ++ ){dp[s].score = inf;for( int i = 0; i < n; i ++ ){if( s&(1<<i) ){pre = s-(1<<i);tmp = dp[pre].Time + sub[i].cost - sub[i].dl;if( tmp < 0 )	tmp = 0;if( dp[pre].score + tmp <  dp[s].score ){//扣分相同，取字典序小的那一个，由于这里j是按从小到达搜索的，默认已是按字典序，不需再处理dp[s].score = dp[pre].score + tmp;dp[s].Time = dp[pre].Time + sub[i].cost;dp[s].pre = i;}}}}
}
void Outup( int s )
{if( s == 0 )	return;int preS = s - (1<<dp[s].pre);Outup( preS );cout<<sub[dp[s].pre].name<<endl;
}
int main()
{#ifndef ONLINE_JUDGE  freopen("data.txt","r",stdin);  #endif  int cas;scanf("%d",&cas);while( cas -- ){scanf("%d",&n);for( int i = n-1; i >= 0; i -- )cin>>sub[i].name>>sub[i].dl>>sub[i].cost;GetDp();printf("%d\n",dp[(1<<n)-1].score);Outup( (1<<n)-1 );}return 0;
}

这篇关于HDU-1074 Doing Homework 状态压缩DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---