[ POI 2005 ] Bank Notes

$\\$

Description

给出 $N$ 种货币的面值 $b_i$ 和个数 $c_i$ ，求最少需要用多少个硬币凑出 $Q$ 元钱，并输出任意一种方案。

$n\le 200,Q,b_i ,c_i\le 2\times 10^4,$ 空间限制 64 M。

$\\$

Solution

空间计算不讲道理

如果不输出方案的话，就是一个普通的多重背包了对吧。

$f[i]$ 表示达到体积为 $i$ 的最少硬币数，然后直接二进制拆分就好了。

考虑转移的时候记录 $pre$ 。

按照一般的动规方式，我们需要记录某一个状态转移自哪一个状态，这一题种，我们只需要记录转移自的上一个体积即可，若未转移指向自己。

但是发现空间爆炸。

分析转移性质，每次做背包的物品大小固定，所以转移自的状态也是确定的，所以我们只需要用一个 $bool $ 数组记录当前位置是否转移过即可。

但是依旧不明白为什么这样空间开的下手算大小在 114 M左右

$\\$

Code



#include<cmath>

#include<cstdio>

#include<cctype>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define N 20010

#define R register

#define gc getchar

using namespace std;

inline int rd(){

  int x=0; bool f=0; char c=gc();

  while(!isdigit(c)){if(c=='-')f=1;c=gc();}

  while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}

  return f?-x:x;

}

bool g[3000][N];

int n,k,tot,b[210],c[210],f[N],bin[30]={1},cnt[210];

struct obj{int v,w,p;}s[3000];

inline void calc(int v,int w){

  for(R int i=k;i>=v;--i)

    if(f[i]>f[i-v]+w) g[tot][i]=1,f[i]=f[i-v]+w;

}

inline void add(int v,int w,int ty){

  s[++tot].v=v; s[tot].w=w;

  s[tot].p=ty; calc(v,w);

}

void dfs(int v,int t){

  if(v==0) return;

  while(!g[t][v]) --t;

  cnt[s[t].p]+=s[t].w;

  dfs(v-s[t].v,t-1);

}

int main(){

  n=rd();

  memset(f,0x3f,sizeof(f)); f[0]=0;

  for(R int i=1;i<=30;++i) bin[i]=(bin[i-1]<<1);

  for(R int i=1;i<=n;++i) b[i]=rd();

  for(R int i=1;i<=n;++i) c[i]=rd();

  k=rd();

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

    for(R int j=0;j<=30;++j){

      if(c[i]<bin[j]) break;

      c[i]-=bin[j];

      add(bin[j]*b[i],bin[j],i);

    }

    if(c[i]) add(c[i]*b[i],c[i],i);

  }

  printf("%d\n",f[k]);

  dfs(k,tot);

  for(R int i=1;i<=n;++i) printf("%d ",cnt[i]);

  return 0;

}

巴特西

[ POI 2005 ] Bank Notes

Description

Solution

Code

最新文章

热门文章