【PAT甲级】1068 Find More Coins (30 分)(背包/DP)
2024-09-06 12:29:48
题意:
输入两个正整数N和M(N<=10000,M<=10000),接着输入N个正整数。输出最小的序列满足序列和为M。
AAAAAccepted code:
#define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
int a[];
int dp[];
int vis[][];
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,m;
cin>>n>>m;
for(int i=;i<=n;++i)
cin>>a[i];
sort(a+,a++n);
for(int i=n;i;--i)
for(int j=m;j>=a[i];--j)
if(dp[j]<=dp[j-a[i]]+a[i]){
dp[j]=dp[j-a[i]]+a[i];
vis[i][j]=;
}
if(dp[m]<m)
cout<<"No Solution";
else{
int i=,j=m;
while(){
if(vis[i][j]){
cout<<a[i];
j-=a[i];
if(j)
cout<<" ";
}
++i;
if(!j)
break;
}
}
return ;
}
最新文章
- 使用SignalR实现服务端消息推送
- 利用反卷积神经网络可视化CNN
- 介绍开源的.net通信框架NetworkComms框架 源码分析(十)DOSProtection
- 快速开发CSS的利器-LESS
- 1128. Partition into Groups(图着色bfs)
- Web应用工作流程总结
- DLL入门浅析(1)——如何建立DLL
- jquery ajax自定义分页组件(jquery.loehpagerv1.0)原创
- Oracle 分页查询与数据去重
- 交给子类: Template Method(模板方法模式)【PHP】
- 用sort方法输出数组
- 插入排序-C#实现
- 使用 MongoDB 存储日志数据
- 【jvisualvm远程监控配置】
- cordova最小化app插件的使用: cordova-plugin-appminimize
- 199. Binary Tree Right Side View 从右侧看的节点数
- Ubuntu 利用 crontab 和 notify-send 定时发送桌面通知,提示该休息啦
- 「LOJ2000~2023」各省省选题选做
- Windows自动登录设置 Windows免密登录
- hMailServer SSL 配置
热门文章
- APL: ANSYS Power Library
- 解决Cannot download ";https://github.com/sass/node-sass/releases/download/binding.nod的问题
- 初识hadoop --- (分布式文件系统 + 分块计算)
- appium---如何判断原生页面和H5页面
- Jmeter学习之-聚合报告详解
- 关于mybatis中sql映射文件模糊查询的使用
- C语言当中int,float,double,char这四个有什么区别?
- 【Python collections】
- 01hive基础操作
- GO学习之 为什么选择GO