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 MathHintIn 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.
题意：有n门课，每门课有截止时间和完成所需的时间，如果超过规定时间完成，每超过一天就会扣1分，问怎样安排做作业的顺序才能使得所扣的分最小
思路：因为最多只有15门课程，可以使用二进制来表示所有完成的状况
例如5，二进制位101，代表第一门和第三门完成了，第二门没有完成，那么我们可以枚举1~1<<n便可以得出所有的状态
然后对于每一门而言，其状态是t = 1<<i，我们看这门在现在的状态s下是不是完成，可以通过判断s&t是否为1来得到
当得出t属于s状态的时候，我们便可以进行DP了，在DP的时候要记录路径，方便之后的输出
#include <iostream>
#include <string>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
const int inf = 1<<30;
struct node
{
string name;
int dead,cost;
} a[50];
struct kode
{
int time,score,pre,now;
} dp[1<<15];
int main()
{
int t,i,j,s,n,end;
cin >> t;
while(t--)
{
memset(dp,0,sizeof(dp));
cin >> n;
for(i = 0; i<n; i++)
cin >> a[i].name >> a[i].dead >> a[i].cost;
end = 1<<n;
for(s = 1; s<end; s++)
{
dp[s].score = inf;
for(i = n-1; i>=0; i--)
{
int tem = 1<<i;
if(s & tem)
{
int past = s-tem;
int st = dp[past].time+a[i].cost-a[i].dead;
if(st<0)
st = 0;
if(st+dp[past].score<dp[s].score)
{
dp[s].score = st+dp[past].score;
dp[s].now = i;
dp[s].pre = past;
dp[s].time = dp[past].time+a[i].cost;
}
}
}
}
stack<int> S;
int tem = end-1;
cout << dp[tem].score << endl;
while(tem)
{
S.push(dp[tem].now);
tem = dp[tem].pre;
}
while(!S.empty())
{
cout << a[S.top()].name << endl;
S.pop();
}
}
return 0;
}
HDU1074：Doing Homework(状态压缩DP),布布扣,bubuko.com
HDU1074：Doing Homework(状态压缩DP)
原文：http://blog.csdn.net/libin56842/article/details/24316493