题解 P4799 [CEOI2015 Day2] 世界冰球锦标赛
djh0314
·
·
个人记录
传送门。
题意
一共有 n 种门票，第 i 种门票的价格为 val_i，预算为 M。
问一共有多少种购买方式满足购买的总花费小于预算。
## 过程
### 切分（$n\le 20$）
依照惯例，我们从部分分打起，看看前四个点，$n\le 20$，我们就可以用状压来解决，换句话说，我们二进制枚举每一个点是否选择，如果满足，那么就使答案 +1。
时间复杂度：$O(2^n)$。
### 切分2（$n\le 40$，$m\le 10^6$）
对于这种情况，也是很明显的，我们可以使用 DP 解决。
## 正解
经过我们第二个部分分我们可以发现，我们的方案数其实是与我们的决策方案是没有关系的，实际上我们所需要的只是我们计算出来的代价和。
在加上我们的部分分 1，我们可以想到，我们用状压分别解决左部分，右部分，然后枚举我们左部分与右部分哪几个部分可以合并。
这个过程，我们排序后 upper_bound 即可。
~~~cpp
inline void solve(int L,int R) {
int len=R-L+1;
int up=(1<<len)-1,ans=0;
for(int j=1; j<=up; ++j) {
tot[j]=tot[j-lowbit(j)]+a[dy[lowbit(j)]+L];
if(tot[j]<=m) ++ans;
}
}
...
int ans=0;
for(int i=0;i<=len1;++i) {
if(sum[i]>m) break;
ans+=upper_bound(tot,tot+len2+1,m-sum[i])-tot;
}
~~~