题意

有\(n \leq 40\)个节点，每个节点有权值\(H \leq 1e9\)和贡献\(v \leq 1e9\)，从任意一个点可以向右跳到一个权值不小于它的节点，并获得该点贡献

可以从任意一个点开始，任意一个点结束

看数据范围可知此题是典型的折半搜索

方法：离散化高度后将数据分为左右两部分，分别DFS出两边的合法状态，然后排序考虑合并

左半部从大到小排序，右半部从小到大排序，统计右半部的各种高度前缀和

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

#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"#include"map"using namespace std;const int MAXN=45;int n,np,mid,o[MAXN];long long c,ans;int H[MAXN],v[MAXN],cnt[2];int lis[MAXN];map
    
      p;struct rpg{    long long v;    int h;}a[2][1<<20];void dfs1(long long val,int h,int tp){    a[0][++cnt[0]]=(rpg){val,h};    if(tp==mid) return;    for(int i=tp+1;i<=mid;++i) if(H[i]>=h) dfs1(val+v[i],H[i],i);    return;}void dfs2(long long val,int lh,int h,int tp){    a[1][++cnt[1]]=(rpg){val,lh};    if(tp==n) return;    for(int i=tp+1;i<=n;++i) if(H[i]>=h) dfs2(val+v[i],lh?lh:H[i],H[i],i);    return;}bool cmp1(rpg a,rpg b){return a.v>b.v;}bool cmp2(rpg a,rpg b){return a.v
     
      o[i-1]);    for(int i=1;i<=n;++i) H[i]=p[H[i]];    mid=1+n>>1;dfs1(0,0,0);dfs2(0,0,0,mid);    sort(a[0]+1,a[0]+cnt[0]+1,cmp1);    sort(a[1]+1,a[1]+cnt[1]+1,cmp2);    a[1][1].h=41;for(int i=1;i<=cnt[1];++i) ++lis[a[1][i].h];    int ct1=1,ct2=1;    while(ct1