BZOJ2073 「POI2004」PRZ 状压DP

问题描述

BZOJ2073

题解

发现 \(n \le 16\) ，显然想到状压

设 \(opt[S]\) 代表过河集合为 \(S\) 时，最小时间。

枚举 \(S\) 的子集，进行转移

枚举子集的方法

对于 \(j\) 为 \(k\) 的子集

当知道 \(j\) 时

for(int k=(j+1)|j;k<=S;k=(k+1)|j)

当知道 \(k\) 时

for(int j=(k-1)&k;j;j=(j-1)&k)

\(\mathrm{Code}\)

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

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
    if(ch=='-') ch=getchar(),fh=-1;
    else fh=1;
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    x*=fh;
}

const int maxn=19;
const int INF=0x3f3f3f3f;

int mx,n;
int opt[1<<17];
int t[maxn],w[maxn];

pair<int,int> calc(int x,int y){
    int res1(0),res2(0);
    for(int i=1;i<=n;i++){
        int k=((x>>(i-1))&1),p=((y>>(i-1))&1);
        if(k==1&&p==0) res1+=w[i],res2=max(res2,t[i]);
    }
    return make_pair(res1,res2);
}

int main(){
    read(mx);read(n);
    for(int i=1;i<=n;i++){
        read(t[i]);read(w[i]);
    }
    memset(opt,0x3f,sizeof(opt));
    opt[0]=0;
    for(int i=1;i<(1<<n);i++){
        for(int j=(i-1)&i;1;j=(j-1)&i){
            int W,T;
            pair <int,int> pr=calc(i,j);
            W=pr.first,T=pr.second;
            if(W<=mx) opt[i]=min(opt[i],opt[j]+T);
            if(j==0) break;
        }
    }
    printf("%d\n",opt[(1<<n)-1]);
    return 0;
}