HDU 1074 Doing Homework （状压DP）

题目

Problem Description
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.

Input
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.

Output
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.

题解

题目的意思就是说给你很多门的课，以及每门课的ddl和耗费时间，超出ddl一天就会扣一分，最少的扣分数和方案。那么这是一道dp题目，然后我就去嗯dp了，但是在dp的过程中，我们发现如果是线性dp，那么在状态转移我们很明显首先要写一个k状态代表拿第几本的书，并且当前拿书的状态需要由前面拿书的状态转移过来，那么就会出现许许多多的问题，比如我前面不同状态所需要的时间不好维护，而且直接枚举第i本选什么看似并不满足最优子结构，所以嗯dp肯定是比较棘手的。你回去再看看题目，就会发现，n<15的数据量，再结合上面的这些缺点那不就是在提醒你状态压缩吗。所以我们写一个状压dp过程中维护pre数组和t数组就可以了。

代码实现

#include<bits/stdc++.h>
using namespace std;
void check_max (int &a,int b) {a=max (a,b);}
void check_min (int &a,int b) {b=min (a,b);}
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=(1<<15)+10;
int n;
int dp[maxn],t[maxn],pre[maxn],death[20],cost[maxn];
char s[20][110];

void output (int k) {
  if (!k) return ;
  output (k-(1<<pre[k]));
  printf ("%s
",s[pre[k]]);
}

void solve () {
  scanf ("%d",&n);
  for (int i=0;i<n;i++) scanf ("%s%d%d",&s[i],&death[i],&cost[i]);
  int k=1<<n;
  for (int i=1;i<k;i++) {
    dp[i]=inf;
    for (int j=n-1;j>=0;j--) {
      int temp=1<<j;
      if (!(temp&i)) continue;
      int now=t[i-temp]-death[j]+cost[j];
      if (now<0) now=0;
      if (dp[i]>dp[i-temp]+now) {
        dp[i]=dp[i-temp]+now;
        t[i]=t[i-temp]+cost[j];
        pre[i]=j;
      }
    }
  }
  printf ("%d
",dp[k-1]);
  output (k-1);
}

int main () {
  int tt;
  scanf ("%d",&tt);
  while (tt--) {
    solve ();
  }
  return 0;
}