题意

一个人为了楼顶的金币要去跳楼，但是不能往更矮的楼上跳。

求在一个长为N的序列中总点权值和大于等于K的不下降序列数。

N<=40，K<=4e10

官方题解

折半搜索的经典例子！N在20范围内搜索能过，40范围内需要折半，由于只能向右跳，所以可以先离散化高度后将数据分为左右两部分，分别DFS出两边的合法状态(每个状态就是合法的大楼高度不下降子序列，其中包含两个属性(子序列中val价值总和，左半边是最后1个楼的高度h，而右半边是第一个楼的高度h))，然后再排序考虑合并。左半部按价值总和从大到小排序，右半部从小到大排序，统计右半部的各种高度前缀和。

双指针从左往右扫，统计合法的方案数。

方法二：只对右半部分按总金币从小到大排序，保持valL+valR≥K && hL≤hR，二分对右半部分查找并匹配左半部分。

本人题解

一看这个K，肯定要开long long ，由于N很小，空间不涉及金币数是绝对没问题的，用暴力搜索是O(2^N)必定会超时。

如果单单是求以 i 开头的金币最多的子序列，我们可以用DP求，如果单单是求以 i 开头的子序列数，我们也可以用DP求，但是题目把它们结合了，而且限制了金币数的下限，虽然我们可以预处理DP判断以 i 开1头的最多金币数是否达标……

没错，只要我们可以O(1)判断以 i 开头的最多金币数是否达标，就可以是很不错的剪枝。

此外，若 i 本身的金币数就达标了，那answer岂不是直接加上以 i 开头的子序列数？

这两个剪枝一加上，我们的搜索就能变快许多倍。而且都可以用DP预处理。

考虑时间复杂度，answer包含的情况我们肯定算过，而不在answer中的方案，我们肯定在序列中第一个无效点就return了，所以最坏情况是O(answer)，可以过。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<vector>

#include<stack>

#include<queue>

#include<map>

#define max(x,y) ((x) > (y) ? (x) : (y))

#define min(x,y) ((x) < (y) ? (x) : (y))

#define abs(x) ((x) < 0 ? -(x) : (x))

#define LL long long

#define lowbit(x) (-(x) & (x))

using namespace std;

LL read() {

	LL f = 1,x = 0;char s = getchar();

	while(s < '0' || s > '9') {if(s == '-') f = -1;s = getchar();}

	while(s >= '0' && s <= '9') {x = x * 10 + s - '0';s = getchar();}

	return x * f;

}

LL n,m,i,j,o,k,cnt;

LL h[45],g[45];

LL dp1[45],dp2[45];//最大金币数，子序列数

LL dfs(int x,LL mon) {

	LL as = 0;

	if(dp1[x] < mon) return 0;

	if(g[x] >= mon) return dp2[x];

	for(int i = x + 1;i <= n;i ++) {

		if(h[i] >= h[x]) {

			as += dfs(i,mon - g[x]);

		}

	}

	return as;

}

int main() {

	n = read();m = read();

	for(int i = 1;i <= n;i ++) {

		h[i] = read();

		g[i] = read();

	}

	for(int i = n;i >= 0;i --) {//DP预处理

		dp1[i] = g[i];

		dp2[i] = 1;

		for(int j = n;j > i;j --) {

			if(h[j] >= h[i]) {

				dp1[i] = max(dp1[i],dp1[j] + g[i]);

				dp2[i] += dp2[j];

			}

		}

	}

	printf("%lld\n",dfs(0,m));

	return 0;

}

San(COCI2017.2)题解的相关教程结束。