标签归档:状压dp

Kick Start 2018 Round B B题

Sherlock and the Bit Strings

构造一个长度为N的只有‘0’和‘1’的串s,满足K个限制(s[A,B]中含有C个1),且这个串在所有满足限制的合法串当中为字典序第P大.

状压dp,f[i][j]:假设前i个字符已固定,且这前i个中最后16个字符为j时的合法方案数(注意j前面的到底是什么我们不用管,看作前缀是固定的,这个结果统计的是前缀之后的部分可以有多少种变化)。我们从后往前转移,最终得到每个位置的情况。如何转移看代码就很清楚了,再次感到熟练位操作对做状压方面的题目很重要。

官方题解开头就讲到固定前缀的合法方案数与字典序第p大的关系,一开始没理解...就是如果串是i开头的话(我们以字典序的顺序来尝试i),f[1][i]>=p,那么第p大就一定是在这f[1][i]方案中了,否则从P中减掉f[1][i](f[1][i]的方案里都是些比P小的,开头字典序比i大时的方案里第P-f[1][i]大的,就是原来所有方案里第P大的),i再转向下一个字典序更大的选择。然后可以一个一个位置构造出这个串。

#include<bits/stdc++.h>
using namespace std;

long long f[105][1<<16];
vector <pair<int,int> > limits[105];
int cnt[1<<16];
int shl[1<<16];

bool check(int i,int last){
    for(int j=0;j<limits[i].size();++j){
        if(cnt[((1<<limits[i][j].first)-1)&last]!=limits[i][j].second){
            return false;
        }
    }
    return true;
}

int main(){
    int T,kase=0;
    scanf("%d",&T);
    for(int i=1;i<(1<<16);++i){
        cnt[i]=cnt[i>>1]+(i&1);
        shl[i]=(i<<1)&((1<<16)-1);
    }
    while(T--){
        int n,k;
        long long p;
        scanf("%d%d%lld",&n,&k,&p);
        for(int i=1;i<=n;++i) limits[i].clear();
        for(int i=1;i<=k;++i){
            int A,B,C;
            scanf("%d%d%d",&A,&B,&C);
            limits[B].push_back(make_pair(B-A+1,C));
        }
        for(int i=0;i<(1<<16);++i){
            if(check(n,i)){
                f[n][i]=1;
            }
            else f[n][i]=0;
        }
        for(int i=n-1;i>0;--i){
            for(int j=0;j<(1<<16);++j){
                if(check(i,j)){
                    f[i][j]=f[i+1][shl[j]]+f[i+1][shl[j]^1];
                    if(f[i][j]>1e18) f[i][j]=1e18+1;
                }
                else f[i][j]=0;
            }
        }

        printf("Case #%d: ",++kase);
        for(int i=1,j=0;i<=n;++i,j=shl[j]){
            if(f[i][j]>=p){
                printf("0");
            }
            else{
                p-=f[i][j];
                j^=1;
                printf("1");
            }
        }
        printf("\n");

    }
    return 0;
}

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;
}

POJ 2411 Mondriaan’s Dream (状态压缩dp)

POJ2411

《算法竞赛进阶指南》P298 状态压缩DP例题

所谓状态压缩DP,就是通过二进制数来记录状态集合,这个二进制数作为DP的维度。

#include<iostream>
using namespace std;
typedef long long ll;

int n,m;
ll f[12][1<<11];
bool in_s[1<<11];

int main(){
    while(cin>>n>>m&&n){
        for(int i=0;i<1<<m;++i){
            bool cnt=0,has_odd=0;//has_odd:已经出现一段奇数个连续的0,cnt:当前是否出现了奇数个0
            for(int j=0;j<m;++j){
                if(i>>j&1) has_odd|=cnt,cnt=0;
                else cnt^=1;
            }
            in_s[i]=has_odd|cnt?0:1;
        }
        f[0][0]=1;
        for(int i=1;i<=n;++i){
            for(int j=0;j<1<<m;++j){
                f[i][j]=0;
                for(int k=0;k<1<<m;++k){
                    if((j&k)==0&&in_s[j|k]){
                        f[i][j]+=f[i-1][k];
                    }
                }
            }
        }
        cout<<f[n][0]<<endl;

    }
    return 0;
}