Luogu5020 货币系统 (完全背包)
2024-10-20 13:36:14
bool型完全背包
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); a <= (c); ++ a)
#define nR(a,b,c) for(register int a = (b); a >= (c); -- a)
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Abs(a) ((a) < 0 ? -(a) : (a))
#define Swap(a,b) a^=b^=a^=b
#define ll long long
#define ON_DEBUG
#ifdef ON_DEBUG
#define D_e_Line printf("\n\n----------\n\n")
#define D_e(x) cout << #x << " = " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt","r",stdin);
#else
#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#endif
struct ios{
template<typename ATP>ios& operator >> (ATP &x){
x = 0; int f = 1; char c;
for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;
while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();
x*= f;
return *this;
}
}io;
using namespace std;
const int N = 250007;
int f[N];
int a[N];
int main(){
//FileOpen();
int Tasks;
io >> Tasks;
while(Tasks--){
int n;
io >> n;
R(i,1,n){
io >> a[i];
}
int ans = n;
sort(a + 1, a + n + 1);
Fill(f, 0);
f[0] = 1;
R(i,1,n){
if(f[a[i]]){
--ans;
continue;
}
R(j,a[i],a[n]){
f[j] |= f[j - a[i]];
}
}
printf("%d\n", ans);
}
return 0;
}
最新文章
- Win7 IIS下启用ASP.NET
- android xutils
- Android异步处理一:使用Thread+Handler实现非UI线程更新UI界面
- [转载]JSON序列化与反序列化
- myeclipse与数据库进行连接(无需写代码进行验证)
- devenv compile errors collection
- 超实用,你get了吗?再也不怕本地文件更新到环境用Linux命令重启服务器了。。。
- SEO为什么越来越难?
- PHP数据结构预热:PHP的迭代器(转)
- Oracle使用并行建索引须要注意的问题
- 每天收获一点点------Hadoop基本介绍与安装配置
- Alfred工具
- Vuejs 页面的区域化与组件封装
- 《HelloGitHub》第 29 期
- SSM框架下 Failed to load resource: the server responded with a status of 404 (Not Found)错误
- C#生成树形结构泛型类
- [CQOI2017]老C的键盘
- ZMQ和MessagePack的简单使用(转)
- Google.ProtocolBuffers.dll 之.Net应用(一)
- EF 多线程TransactionScope事务异常";事务EFTransaction类定义:与另一个进程被死锁在 锁 资源上,并且已被选作死锁牺牲品。请重新运行该事务。";
热门文章
- MongoDB 体系结构与数据模型
- typescript 的安装和检测是否安装成功
- 腾讯产品快速尝鲜,蓝鲸智云社区版V6.1灰度测试开启
- [学习笔记] pd_ds黑科技
- VSCode进一步深入了解学习
- dotnet core 也能协调分布式事务啦!
- DS18B20数字温度计 (三) 1-WIRE总线 ROM搜索算法和实际测试
- HMS Core 视频编辑服务开放模板能力,助力用户一键Get同款酷炫视频
- bat-注册表修改win11右键风格
- Task.Run(), Task.Factory.StartNew() 和 New Task() 的行为不一致分析