题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1074
题目大意：有N个作业（N<=15)，每个作业需耗时，有一个截止期限。超期多少天就要扣多少分。问最少被扣多少分，且按字典序输出做作业顺序。
解题思路：
集合上的DP问题。也就是状态压缩DP。
用二进制位表示做作业的顺序。总bit=1<<15。
对于状态i，枚举当前的作业j，如果i&(1<<(j-1))，则表示当前状态含有作业j。
t^=(1<<(j-1))，还原出还没做j作业之前的状态，现在就有now和pre两个状态了。
计算pre状态下做j作业的扣分情况，+cost[j]-dead[j]，没过期得到负数改为0。
dp转移时顺便记录下当前状态的日期，以及状态i做的是哪个作业j。
注意：因为题目要求是输出字典序小的方案，所以应该倒序循环当前作业j。
这里把思路倒一下，记录的是当前的作业，也就是后做的作业，如果正序循环，则表示先做字典序大的作业，后做字典序小的作业。
正好和题目要求相反了。
最后dp[bit-1]就是结果。
递归打印方案，从bit-1开始，每次^个(1<<j)，递归终点则还原出一开始做的作业，输出即可。
#include "cstdio"
#include "string"
#include "iostream"
#include "cstring"
using namespace std;
#define maxn 1<<15
int dead[],cost[],dp[maxn],T[maxn],pre[maxn];
string sub[];
void output(int x)
{
if(!x) return;
output(x^(<<pre[x]));
cout<<sub[pre[x]]<<endl;
}
int main()
{
//freopen("in.txt","r",stdin);
ios::sync_with_stdio(false);
int t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int bit=<<n;
for(int i=;i<n;i++)
cin>>sub[i]>>dead[i]>>cost[i];
for(int i=;i<bit;i++)
{
dp[i]=<<;
for(int j=n-;j>=;j--)
{
int tt=<<j,reduce;
if(!(i&tt)) continue;
tt=i^tt;
reduce=T[tt]+cost[j]-dead[j];
reduce=reduce<?:reduce;
if(dp[tt]+reduce<dp[i])
{
dp[i]=dp[tt]+reduce;
T[i]=T[tt]+cost[j];
pre[i]=j;
}
}
}
printf("%d\n",dp[bit-]);
output(bit-);
memset(pre,,sizeof(pre));
}
}
| 11693089 | 2014-09-21 01:25:25 | Accepted | 1074 | 15MS | 676K | 1166 B | C++ | Physcal |