luogu题解 P5020 【货币系统 】
2024-08-31 22:30:57
思路
判断钱数是否可以转化为其他钱数的和
与楼下不同,我没有用sort。而是用了一个数组来特判。
思路其实只是简单dp。
详见代码。
#include<cstdio>
using namespace std;
int t;
int main()
{
scanf("%d",&t);
while(t>0)
{
t--;
int n;
scanf("%d",&n);
int a[30000],d[30000]={0},c=0,f[30000]={0};
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]>c)c=a[i];
d[a[i]]=-1;//注意,d数组开了特判,不用sort原因
}
int jss=n;
for(int i=1;i<=c;i++)//哈希
{
int dd=0;//确保只减一次
for(int j=1;j<=n;j++)
{
if(i-a[j]==0)f[i]=a[j];//f[i]可以设为bool
//f[i]=a[j]中a[j]无实际意义
if(i-a[j]>0)
if(f[i-a[j]]!=0)
{
if(d[i]==-1&&dd==0)jss--,dd=1;
f[i]=f[i-a[j]]+a[j];
}
}
}
printf("%d\n",jss);
}
}
加油,我们离神犇会越来越近,祝大家noip2018RP++;
最新文章
- iOS开发--弹窗多选、单选框架
- Python基础8- 序列
- QWidget::paintEngine: Should no longer be called
- 说说怎么写clean code
- 转:python webdriver API 之鼠标事件
- Visual Studio 2010下载 + 附破解方法
- 使用shiro标签遇到的部分问题的解决思路
- [ASP.NET]以iTextSharp手绘表格并产生PDF下载
- Java7新特性
- web页面开发相关基础
- Effective C++笔记之Item49【了解new-handler的行为】
- Mac下配置Nginx负载均衡
- linux_FTP连接失败
- Pytorch 报错总结
- [转载] erp开发-数据查询优化方法
- Civil 3d设置横断面图样式
- VMware vSphere client 中英文语言界面设置
- easyui 时间定格为 时分
- 20155331 丹增旦达 2006-2007-2 《Java程序设计》第二周学习总结
- Gcov 详解 + 内核函数覆盖率测试方法详述及产生错误解决办法
热门文章
- SilverlightMVVM模式中的数据校验
- 原创-使用pywinauto进行dotnet的winform程序控制(一)
- 短视频技术详解:Android端的短视频开发技术
- spring 5.x 系列第17篇 —— 整合websocket (xml配置方式)
- 剖析Unreal Engine超真实人类的渲染技术Part 2 - 眼球渲染
- python多线程爬取图片二
- 浅谈Linq查询
- Java中字符串的一些常用操作方法
- scrapy实战5 POST方法抓取ajax动态页面(以慕课网APP为例子):
- 在Ubuntu16.04 TLS 安装LAMP