[BZOJ] 4145: [AMPPZ2014]The Prices

设\(f[S][i]\)表示考虑到第\(i\)家店，已经买了集合\(S\)内的物品

一个朴素的想法是枚举子集转移

\[f[S][i]=\min\{f[T][i-1]+cost[S\oplus T][i]+d[i]\}
\]

这样做是\(O(n3^m)\)的，不太可行

可行一些的方法是这样的，考虑到枚举子集会重复很多状态

（类比[BZOJ] 2064: 分裂）

实际上是可以用单个元素递进转移的

也就是

\[f[S][i]=\min\{f[S-\{j\}][i]+cost[j]\}
\]

然后再比较在第\(i\)家买是否合适

\[f[S][i]=\min\{f[S][i]+d[i],f[S][i-1]\}
\]

这样的复杂度是\(O(nm2^m)\)的（实际上也大的一匹..）

但是状压常数小，也就这样过了

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<bitset>

using namespace std;

inline int rd(){

  int ret=0,f=1;char c;

  while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;

  while(isdigit(c))ret=ret*10+c-'0',c=getchar();

  return ret*f;

}

#define space() putchar(' ')

#define nextline() putchar('\n')

void _(int x){if(!x)return;_(x/10);putchar('0'+x%10);}

void out(int x){if(!x)putchar('0');_(x);}

const int MAXN = 17;

inline void upmax(int &x,int y){x=max(x,y);}

inline void upmin(int &x,int y){x=min(x,y);}

int n,m;

int d[105],f[1<<MAXN],g[1<<MAXN];

int c[105][MAXN];

int main(){

  memset(g,0x3f,sizeof(g));

  n=rd();m=rd();

  for(int i=1;i<=n;i++){

    d[i]=rd();

    for(int j=0;j<m;j++)c[i][j]=rd();

  }

  g[0]=0;

  for(int i=1;i<=n;i++){

    memset(f,0x3f,sizeof(f));

    f[0]=d[i];

    for(int s=0;s<(1<<m);s++){

      for(int j=0;j<m;j++)

        if(s&(1<<j))

          upmin(f[s],min(g[s^(1<<j)]+d[i],f[s^(1<<j)])+c[i][j]);

      upmin(g[s],f[s]);

    }

  }

  cout<<g[(1<<m)-1];

  return 0;

}

巴特西

[BZOJ] 4145: [AMPPZ2014]The Prices

最新文章

热门文章