【bzoj4800】: [Ceoi2015]Ice Hockey World Championship dfs
2024-08-21 08:21:46
【bzoj4800】: [Ceoi2015]Ice Hockey World Championship
N<=40所以如果直接dfs背包会TLE
考虑Meet-in-the-middle
如果把N个物品分成前后A B两段分别背包
分别在A B中可行的方案的花费记录在a b中
答案就是a[i]+b[j]<=M的个数
把a b排序 然后序列就是单调的了
两个指针扫一遍就好了
/* http://www.cnblogs.com/karl07/ */
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long ll n,m,mid,ans;
ll c[],a[][],ca[]; void dfs(int p,int x,ll cost){
if (cost>m) return;
if ((x>=mid && p==) || (x>=n && p==)){
a[p][++ca[p]]=cost;
return;
}
dfs(p,x+,cost+c[x+]);
dfs(p,x+,cost);
} int main(){
scanf("%lld%lld",&n,&m);
for (int i=;i<=n;i++) scanf("%lld",&c[i]);
mid=n/;
dfs(,,);
dfs(,mid,);
sort(a[]+,a[]+ca[]+);
sort(a[]+,a[]+ca[]+);
for (int l=,r=ca[];l<=ca[] && r>=;ans+=r,l++) while (a[][l]+a[][r]>m) r--;
printf("%lld\n",ans);
return ;
}
竟然有Rank4(2017.3.31)。。好快啊。。
最新文章
- hdu2005第几天?
- 从.NET平台调用Win32 API
- [C#.net]PostMessage与SendMessage的区别
- 东大OJ-1588: Routing Table
- JAVA编程规则
- Rewrite Path in Asp.Net MVC Project
- POJ 3280 Cheapest Palindrome(DP 回文变形)
- 把测试app打包成ipa文件
- mklink命令转移win7系统盘文件夹users和programdata(附xp的方法)
- 用SHELL与列表处理了件尴尬事
- BZOJ 2783 JLOI 2012 树 乘+二分法
- CSharp设计模式读书笔记(8):桥接模式(学习难度:★★★☆☆,使用频率:★★★☆☆)
- aync await 进一步探索
- Visual Studio 2013创建自定义多项目模版
- Linux命令_cp
- 编写基于Property-based的单元测试
- 基本css说明
- 【下一代核心技术DevOps】:(四)私有镜像库阿里云Docker服务使用
- 一:理解ASP.NET的运行机制(例:通过HttpModule来计算页面执行时间)
- BZOJ 1834 网络扩容 最大流+最小费用流