洛谷P1441 砝码称重
2024-09-04 12:15:39
P1441 砝码称重
题目描述
现有n个砝码,重量分别为a1,a2,a3,……,an,在去掉m个砝码后,问最多能称量出多少不同的重量(不包括0)。
输入输出格式
输入格式:
输入文件weight.in的第1行为有两个整数n和m,用空格分隔
第2行有n个正整数a1,a2,a3,……,an,表示每个砝码的重量。
输出格式:
输出文件weight.out仅包括1个整数,为最多能称量出的重量。
输入输出样例
输入样例#1:
3 1
1 2 2
输出样例#1:
3
说明
【样例说明】
在去掉一个重量为2的砝码后,能称量出1,2,3共3种重量。
【数据规模】
对于20%的数据,m=0;
对于50%的数据,m≤1;
对于50%的数据,n≤10;
对于100%的数据,n≤20,m≤4,m<n,ai≤100。
/*
看到数据范围那么小,就直接暴力了,但是提高+/省选-的题怎么可能这么好做。。
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 25
using namespace std;
int a[maxn],b[maxn],c[maxn],n,m,tot,ans,ansnow;
bool vis[];
void count(int pos,int sum){
if(!vis[sum]&&sum!=){
vis[sum]=;
ansnow++;
}
if(pos==tot+)return;
count(pos+,sum);
count(pos+,sum+c[pos]);
}
void dfs(int pos,int cnt){
if(cnt==m){
memset(vis,,sizeof(vis));
ansnow=;
int num=;
for(int i=;i<=n;i++)
if(b[i]!=-)c[++num]=b[i];
count(,);
ans=max(ans,ansnow);
return;
}
if(pos==n+)return;
if(n-pos+<m-cnt)return;
dfs(pos+,cnt);//不删掉
b[pos]=-;
dfs(pos+,cnt+);
b[pos]=a[pos];
}
int main(){
scanf("%d%d",&n,&m);tot=n-m;
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
}
dfs(,);
cout<<ans;
}
60分 暴力TLE
/*
直接爆搜删去哪些砝码,统计方案数的时候用一个01背包就可以了
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 25
using namespace std;
int a[maxn],b[maxn],c[maxn],n,m,tot,ans,ansnow,f[];
void count(){
memset(f,,sizeof(f));
f[]=;
for(int i=;i<=n-m;i++)
for(int j=;j>=c[i];j--)
f[j]+=f[j-c[i]];
for(int i=;i<=;i++)
if(f[i])ansnow++;
}
void dfs(int pos,int cnt){
if(cnt==m){
ansnow=;
int num=;
for(int i=;i<=n;i++)
if(b[i]!=-)c[++num]=b[i];
count();
ans=max(ans,ansnow);
return;
}
if(pos==n+)return;
if(n-pos+<m-cnt)return;
dfs(pos+,cnt);//不删掉
b[pos]=-;
dfs(pos+,cnt+);
b[pos]=a[pos];
}
int main(){
scanf("%d%d",&n,&m);tot=n-m;
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
}
dfs(,);
cout<<ans;
}
100分 搜索+dp
最新文章
- 配置windows路由表,使电脑同时连接内网外网方法
- Java 项目优化实战
- DWG2SHP DXF2SHP 如何把AutoCAD的DWG,DXF文件转换为Esri ArcGIS的Shape文件
- Linux内核--网络栈实现分析(九)--传输层之UDP协议(下)
- phpcms万能字段如何使用php方法
- 【QT】C++ GUI Qt4 学习笔记1
- What books does Bjarne Stroustrup suggest to master C++?
- This Android SDK requires Android Developer Toolkit version 23.0.0 or above
- SharePoint 2010 PowerShell 系列 之 备份、还原、部署 .WSP
- android.util.AndroidRuntimeException: requestFeature() must be called before adding content解决办法
- 【POJ2482】【线段树】Stars in Your Window
- 01UITextField基础知识
- 那天有个小孩教我WCF[一][1/3]
- 移动HTML 5前端性能优化指南(转载)
- 你是否也在学习ES6 Promise时遇到过这个问题?
- 《k8s-1.13版本源码分析》- Informer 机制
- 关于苹果手机微信端 position: fixed定位top导航栏问题
- SSE图像算法优化系列五:超高速指数模糊算法的实现和优化(10000*10000在100ms左右实现)。
- 第10月第21天 手势识别 开屏广告 Xcode快捷键
- MySQL备份与恢复-innobackupex