Gym-102006F Pretests 状压DP

题意

对于一道题目，给定\(t\)个样例\(n\)个提交，每个提交会对其中的某些样例，若通过记作\(1\)否则\(0\)

给定每个人的提交情况，每评测一个样例需要花费单位时间

求出如何安排样例的顺序可以使测试的总时间最小

分析

看到数据范围想到暴力或者状压，暴力复杂度似乎又不够，于是想到DP

令\(dp_i\)表示状态为\(i\)时还需要的最少的花费，那么每次递推到新的状态代价显然是此时还有多少人要进行评测

现在问题转化为了如何求出\(cnt\)数组，发现它实际上是超集的和，直接暴力求\(O(3^n)\)，若用之前学过的高位前缀和可以做到\(O(n 2^n)\)

代码

const int maxn = 2e5 + 5;
int t;

int dfs(int s,vector<int>&cnt,vector<int>&dp,vector<pii>&path){
  if(s == (1 << t) - 1) return 0;
  if(dp[s] != 1e9) return dp[s];
  int mi = 1e9;
  int tag = -1;
  for(int i = 0;i < t;i++){
    if(!((s >> i) & 1)){
        int now = cnt[s] + dfs(((1 << i)|s),cnt,dp,path);
        if(dp[s] > now) dp[s] = now,mi = (1 << i)| s,tag = i; 
    }
  }
  path[s] = make_pair(mi,tag);
  return dp[s];
}


void print(int s,vector<pii>&path){
  if(s == (1 << t) - 1) return;
  cout << path[s].second +  1 << ‘ ‘;
  print(path[s].first,path);
}

void solve(){
  for(int i = 0;i < 25;i++) st[i].reset();
  t = rd();
  int n = rd();
  vector<vector<int>> mp(n + 1,vector<int>(t + 1));
  vector<int> dp((1 << t) + 1,1e9);
  vector<int> cnt((1 << t) + 1,0);
  vector<pii> path((1 << t) + 1);
  for(int i  = 1;i <= n;i++){
  	int s = 0; 
    for(int j = 1;j <= t;j++)
        scanf("%1d",&mp[i][j]),mp[i][j] ? s |= (1 << (j - 1)) : 0;
    cnt[s]++;
  }
  for(int j = 0;j < t;j++)
  	for(int i = 0;i < 1 << t;i++)
  		if(!(i >> j & 1)) cnt[i] += cnt[i ^ (1 << j)];
  cout << dfs(0,cnt,dp,path) << ‘\n‘;
  print(0,path);
  puts("");
}

int main(){
	freopen("tests.in","r",stdin);
  int T = rd();
  while(T--){
    solve();
  }
}

Gym-102006F Pretests 状压DP

原文：https://www.cnblogs.com/hznumqf/p/14659642.html