首页 > 代码库 > BZOJ 2073: [POI2004]PRZ [DP 状压]

BZOJ 2073: [POI2004]PRZ [DP 状压]

传送门

水题不解释

这道题的主要目的在于记录一个枚举子集的技巧

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;typedef long long ll;const int N=18,S=(1<<16)+5,INF=1e9;inline int read(){    char c=getchar();int x=0,f=1;    while(c<0||c>9){if(c==-)f=-1;c=getchar();}    while(c>=0&&c<=9){x=x*10+c-0;c=getchar();}    return x*f;}int m,n,a[N],w[N];int f[S];int main(){    //freopen("in","r",stdin);    m=read();n=read();    for(int i=0;i<n;i++){        a[i]=read(),w[i]=read();        f[1<<i]=a[i];    }    int All=1<<n;    memset(f,0x3f,sizeof(f));    f[0]=0;    for(int s=0;s<All;s++){        int sum=0,slow=0;        for(int i=0;i<n;i++)             if((1<<i)&s) sum+=w[i],slow=max(slow,a[i]);        if(sum<=m) f[s]=slow;        else for(int t=s&(s-1);t;t=s&(t-1)) f[s]=min(f[s],f[t]+f[s^t]);    }    printf("%d",f[All-1]);}

 

BZOJ 2073: [POI2004]PRZ [DP 状压]