货币系统[完全背包][NOIP2018]

本文主要是介绍货币系统[完全背包][NOIP2018]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

考场上没有想出来完全背包,写的暴搜dfs

其实f[i]=1 表示i这个价值的货币出现过

转移方程 

---

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<cctype>
#include<algorithm>
#define N 205
#define A 25050
using namespace std;
int T,n,a[N],s[N],f[A];
int ans,top,last;
int read(){int cnt=0,f=1;char ch=0;while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch))cnt=cnt*10+(ch-'0'),ch=getchar();return cnt;
}
bool check(int l,int x){for(int i=a[l];i<=x;i++)for(int j=1;j<=l;j++)f[i]|=f[i-a[j]];return f[x]==1;
}
int main(){T=read();while(T--){n=read(); top=0; ans=0 , last=0;memset(f,0,sizeof(f)); f[0]=1;for(int i=1;i<=n;i++) a[i]=read();sort(a+1,a+n+1);for(int i=1;i<=n;i++){if(!check(last,a[i])) ans++,last=i;}printf("%d\n",ans);}return 0;
}

 

这篇关于货币系统[完全背包][NOIP2018]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---