NOIp2018D1T2 货币系统【分析&完全背包】
2024-08-30 06:54:36
看到题目瞬间想起某凯的疑惑,感觉不会做....然后观察样例可以知道,去掉原来货币系统中能够被其他币值凑出来的数就是答案(样例分析法),然后就完事了(huaji)。
简单理解一下吧:
首先,去掉原来货币系统中能够被其他币值凑出来的数形成的新的货币系统能够凑出原来就能够凑出来的数,这个很好理解。设原来的货币系统为$A$,假设存在一个比上文所述更优的答案货币系统为$B$,则有$x$属于$A$,$x$不能由$A$中的一些数拼成,且$x$不属于$B$,$x$能由$B$中的一些数拼成。那么$B$中一定存在一个比$x$小的数,他不属于$A$而且也不能由$A$中的数凑出来,否则$A$就可以凑成$x$了。
所以直接写个完全背包判断能不能构成这个数就好了。
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<map>
#include<iostream>
#include<stack>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define N 105
#define M 25001
int rd()
{
int f=,s=;char c=getchar();
while(c<''||c>''){if(c=='-') f=-;c=getchar();}
while(c>=''&&c<=''){s=(s<<)+(s<<)+(c^);c=getchar();}
return f*s;
}
int n;
int a[N];
bool f[M+];
int cnt;
int main()
{
int T=rd();
while(T--)
{
n=rd();
for(int i=;i<=n;i++)
a[i]=rd();
sort(a+,a+n+);
memset(f,,sizeof(f));
cnt=;
f[]=;
for(int i=;i<=n;i++)
{
if(f[a[i]])
{
cnt++;
continue;
}
for(int j=a[i];j<=M;j++)
if(f[j-a[i]])
f[j]=; }
printf("%d\n",n-cnt);
}
return ;
}
Code
最新文章
- Jsonp原理就是这么简单
- MVC实用架构设计(三)——EF-Code First(3):使用T4模板生成相似代码
- PMP 第九章 项目人力资源管理
- SQLSERVER建立MYSQL连接服务器
- CLR via C#深解笔记一 - CLR &; C# 基础概念
- Java-TCP Socket编程
- 《zw版&#183;Halcon-delphi系列原创教程》航母舰载机&#183;视觉定位标志的识别代码
- DBA_Oracle PFile and SPFile文件的管理和使用(案例)
- asp.net gridview中增加单击单元格事件
- linux file命令
- MVC Razor中 如何截断字符串
- paip.最新的c++ qt5.1.1环境搭建跟hello world
- C# - 委托_求定积分通用方法
- 由自动装箱和拆箱引发我看Integer源码
- mysql索引类型和索引方法
- golang使用Nsq
- Flutter
- AJAX技术主要包含的四个组件
- spring cloud:config-server中@RefreshScope的";陷阱";
- CSS多行文字垂直居中的两种方法