leetcode-go/bailian/4149.term-project/main.cc

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int L = 51;
const int N = 15;
const int INF = 1 << 30;

struct Project {
  char s[L];
  int d;
  int c;
};

Project pro[N];

struct Dp {
  int pre;  // Previous node
  int cur;  // Current node
  int min;  // Minimum score
  int fin;  // The finish date
};

Dp dp[1 << N];

vector<int> get_path(int i) {
  vector<int> path;
  while (i) {
    path.push_back(dp[i].cur);
    i = dp[i].pre;
  }
  reverse(path.begin(), path.end());
  return path;
}

int main() {
  int t, n;
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)  // Don't neet to add & for pro[i].s
      scanf("%s %d %d", pro[i].s, &pro[i].d, &pro[i].c);
    dp[0].min = 0;
    dp[0].fin = 0;
    dp[0].pre = -1;
    int fin = (1 << n) - 1;
    // dp[i] = dp[i ^ (1 << k)] + min{score(i, k): k in i}
    for (int i = 1; i <= fin; i++) {
      dp[i].min = INF;
      for (int j = 0, j_ = 1; j < n; j++, j_ <<= 1) {
        if (i & j_) {
          int pre = i ^ j_;
          int tmp_fin = dp[pre].fin + pro[j].c;
          int tmp_min = tmp_fin - pro[j].d;
          tmp_min = max(0, tmp_min);
          if (dp[pre].min + tmp_min < dp[i].min) {
            dp[i].pre = pre;
            dp[i].cur = j;
            dp[i].min = dp[pre].min + tmp_min;
            dp[i].fin = tmp_fin;
          }
          // Get the path which has smaller lexicographic order.
          if (dp[pre].min + tmp_min == dp[i].min) {
            vector<int> p1 = get_path(dp[i].pre);
            vector<int> p2 = get_path(pre);
            if (p2 < p1) {
              dp[i].pre = pre;
              dp[i].cur = j;
              dp[i].fin = tmp_fin;
            }
          }
        }
      }
    }
    printf("%d\n", dp[fin].min);
    vector<int> path = get_path(fin);
    for (int i : path) printf("%s\n", pro[i].s);
  }
  return 0;
}