洛谷 P1120 小木棍[数据加强版]
2024-09-06 08:57:01
这道题可能是我做过的数据最不水的一道题……
题目传送门
这题可以说是神剪枝,本身搜索并不算难,但剪枝是真不好想(好吧,我承认我看了题解)……
剪枝:
- 用桶来存储木棍
- 在输入的时候记录下最长的木棍和最短的木棍和木棍的总长
- 搜索时保证目前答案能整除木棍
- 搜索时记录下上一层的木棍长度,然后从该木棍的长度到小进行枚举
- 如果搜回来发现当前木棍长度等于答案,那么直接return
大的剪枝就这些了,还有一些小剪枝,具体还是看代码吧:
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int read(){
int k=0; char c=getchar();
for(;c<'0'||c>'9';) c=getchar();
for(;c>='0'&&c<='9';c=getchar())
k=(k<<3)+(k<<1)+c-48;
return k;
}
int n,tot,a[101];
int maxn,minn=100000;
void dfs(int sum,int ans,int hhh,int maxx){
if(!hhh){
printf("%d",ans);
exit(0);
}
if(sum==ans){
dfs(0,ans,hhh-1,maxn);
return ;
}
for(register int i=maxx;i>=minn;i--){
if(sum+i<=ans&&a[i]){
a[i]--;
//cout<<a[i]<<endl;
dfs(sum+i,ans,hhh,i);
a[i]++;
if(sum==0||sum+i==ans)
break;
}
}
return ;
}
int main(){
//freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);
n=read();
for(register int i=1;i<=n;i++){
int x=read();
if(x>50) continue;
a[x]++; tot+=x;
maxn=max(maxn,x);
minn=min(minn,x);
}
int zz=tot>>1;
for(register int i=maxn;i<=zz;i++){
if(tot%i==0){
dfs(0,i,tot/i,maxn);
}
}
printf("%d",tot);
return 0;
}
/* 赠送一组数据 QWQ
64
1 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 1 1 2 2 1 2 2 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 1 1
13
*/
最新文章
- 【Linux】虚拟机安装Archlinux
- js原声快速实现选项卡
- acm系统开发笔记
- 关于markdown的学习
- Memcache升级版:CouchBase的安装配置与使用说明
- phalcon: 视图分层渲染,或包含其他页面
- C++11包装引用
- Excel VBA 快捷键 代码
- grunt serve Fatal error: Port 35729 is already in use by another process.
- Riak VClock
- Oracleclient+PLSQL Developer实现远程登录Oracle数据库
- 简易RPC框架-心跳与重连机制
- 一款非常推荐的用户界面插件----EasyUI
- Python之list列表方法详解
- Capacitor 新一代混合应用“神器” 会代替Cordova吗??
- python 对Excel表格的写入
- HDU 3537 Daizhenyang&#39;s Coin
- ES系列十三、Elasticsearch Suggester API(自动补全)
- hdu 1983(BFS+DFS) 怪盗Kid
- 百度Web Uploader组件实现文件上传之分片上传(一)