Input
第一行两个数n，m代表物品数量及钱数
第二行n个数，代表每个物品的价格
n<=40，m<=10^18
Output
一行一个数表示购买的方案数
（想怎么买就怎么买，当然不买也算一种）
Sample Input
5 1000
100 1500 500 500 1000
100 1500 500 500 1000
Sample Output
8
把序列分成两半，分别搜出所有状态。然后排个序双指针解决。
代码：
1、JS-HTML DOM remove() 方法
2、剑指Offer 20 表示数值的字符串
3、Very Long Suffix Array
4、c++ virtual总结
5、【转】Android中的事件分发和处理
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
typedef unsigned long long ll;
int n,mid;
ll w[50],a[2000050],b[2000050],m;
int la,lb;
void dfs1(int dep,ll sum) {
if(dep==mid) {
a[++la]=sum; return ;
}
if(w[dep+1]+sum<=m) dfs1(dep+1,sum+w[dep+1]);
dfs1(dep+1,sum);
}
void dfs2(int dep,ll sum) {
if(dep==n) {
b[++lb]=sum; return ;
}
if(w[dep+1]+sum<=m) dfs2(dep+1,sum+w[dep+1]);
dfs2(dep+1,sum);
}
int main() {
//freopen("shopping.in","r",stdin);
//freopen("shopping.out","w",stdout);
scanf("%d%llu",&n,&m);
int i;
for(i=1;i<=n;i++) {
scanf("%llu",&w[i]);
}
if(n==1) {
printf("%d\n",1+(w[1]<=m)); return 0;
}
mid=(n+1)>>1;
dfs1(0,0);
dfs2(mid,0);
int j=lb;
sort(a+1,a+la+1); sort(b+1,b+lb+1);
ll ans=0;
for(i=1;i<=la;i++) {
while(j&&b[j]+a[i]>m) j--;
if(j==0) break;
ans+=j;
}
printf("%llu\n",ans);
}
优质内容筛选与推荐>>
1、JS-HTML DOM remove() 方法
2、剑指Offer 20 表示数值的字符串
3、Very Long Suffix Array
4、c++ virtual总结
5、【转】Android中的事件分发和处理