HDU – 1074 Doing Homework (状态压缩dp)

HDU 1074

状态转移方程:
当currutTime+consume[k]-deadline[k]>0,
f[i|(1<<k)] = min( f[i|(1<<k)] , f[i]+currentTime+comsume[k]-deadline[k] );
否则,
f[i|(1<<k)] = min( f[i|(1<<k)] , f[i] );

i表示已经完成的作业情况,k表示第k个作业。对同一个状态 m=(i|(1<<k)),i和k的组合能有多种, 因为输入是按字典序给出的,让到达m时i尽量小,则能保证输出是字典序最小(即i从小到大遍历)。

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#define maxn 0x3f3f3f3f
#define ll long long
using namespace std;

int f[1 << 15];
int t[1 << 15];
int pre[1<<15];
int n;
struct homework {
  string s;
  int D;
  int C;
} a[20];

void print(int m) {
   if(m) {
    for(int i=0;i<n;++i){
      if((1<<i)&(m-pre[m])){
        print(pre[m]);
        cout<<a[i].s<<endl;
        break;
      }
    }
  }
}

int main() {
  int T;
  cin >> T;
  while (T--) {
    cin >> n;
    for (int i = 0; i < n; ++i) {
      cin >> a[i].s >> a[i].D >> a[i].C;
    }
    memset(t, 0x3f, sizeof(t));
    memset(f, 0x3f, sizeof(f));
    t[0] = 0;
    f[0] = 0;
    for (int i = 0; i < (1 << n); ++i) {
      for (int k = 0; k < n; ++k) {
        if ((i &(1 << k) )==0) {
          if ((t[i] + a[k].C >= a[k].D)) {
            if (f[i|(1<<k)] > f[i] + t[i] + a[k].C - a[k].D) {
              f[i|(1<<k)] = f[i] + t[i] + a[k].C - a[k].D;
              t[i|(1<<k)] = t[i] + a[k].C;
              pre[i|(1<<k)] = i;
            }
          } else {
            if (f[i|(1<<k)] > f[i]) {
              f[i|(1<<k)] = f[i];
              t[i|(1<<k)] = t[i] + a[k].C;
              pre[i|(1<<k)] = i;
            }
          }
        }
      }
      //cout<<f[i]<<" "<<t[i]<<endl;
    }
    cout << f[(1 << n) - 1] << endl;
    print((1 << n) - 1);
  }
  return 0;
}