[COCI 2017-2018-2]

san(1s64M)

游戏世界中有N个楼从左到右排列，从左到右编号为1到N，第i幢楼的高度为Hi,楼上的金币数为Gi,游戏可以从任意一个楼开始且包涵几步。每一步玩家可以从当前位置向右跳（可以跳过一些楼）但必须跳到不低于当前楼的高度的楼上。他到了楼上后，可以得到楼上的金币。他可以在跳任意步（可以是零步）后结束游戏，但是要保证收到的金币数要大于等于K，现在想知道共有多少不同的种方案满足游戏。两个方案不同是指至少有一个楼不一样的方案。

输入：

第一行两个数N (1 ≤ N ≤ 40) and K (1 ≤ K ≤ 4 · 10¹⁰ )

接下来N行，每行两个正整数，第i行用Hi和Gi表示第i个楼的高度和上面的金币。 (1 ≤ Hi, Gi ≤ 10⁹)

输出一行一个数，表示方案总数。

In test cases worth 40% of total points, it will hold N ≤ 20.

SAMPLE TESTS

input input input

4 6

2 1

6 3

7 2

5 6

Output

样例1对应的方案 {1, 2, 3}, {1, 4} and {4}

题目大意：
给定N座楼，它们有各自的高度与收益，每次任意位置开始，可以跳到右边高度大于等于它的楼，到达可得收益，
求收益>=K的方案数

分析：
方法一：
N<=40可以搜索+剪枝，可能可以暴力过一过，考场上写的过了
剪枝：
预处理出mx 表示这个点往后跳可以获得的最大收益搜索时可以很好预判
预处理出way 表示这个点开始跳的方案数当我们已经满足tot>=K 可以直接加上way 退出

#include<bits/stdc++.h>
using namespace std;

long long mx[45];
long long way[45];
int n;long long K;

struct Build
{
    int h,v;
}edge[45];

long long ans;
void dfs(int now,long long tot)
{
    if(tot>=K) {ans+=way[now];return ;}
    if(now==n+1) return ;
    for(int i=now+1;i<=n;i++) 
    {
        if(edge[i].h>=edge[now].h)
        {
            if(tot+mx[i]<tot) continue;
            dfs(i,tot+edge[i].v);
        }
    }
}

int main()
{
    freopen("san.in","r",stdin);
    freopen("san.out","w",stdout);
    scanf("%d%lld",&n,&K);
    for(int i=1;i<=n;i++) {scanf("%d%d",&edge[i].h,&edge[i].v);}
    mx[n]=edge[n].v;way[n]=1;
    for(int i=n-1;i>=1;i--)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(edge[i].h<=edge[j].h) mx[i]=max(mx[i],mx[j]),way[i]+=way[j];
        }
        mx[i]+=edge[i].v;way[i]++;
    }
    
    for(int i=1;i<=n;i++)
    dfs(i,edge[i].v);
    
    printf("%lld
",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

View Code

方法二：
还是看N<=40，直接二进制枚举不完，发现可以拆成两部分
mid=20 就可以直接枚举
我们可以得到两部分分别的值，并把前一部分的结尾与w记录，把后一部分的开头与w记录
因为分别的求了还要求跨区间的部分
我们现在需要满足s1[i].w+s2[j].w>=K&&s1[i].last<=s2[i].first
二维限制，先把w排序，pos从第一部分从右往左我们发现是递减，那么是单调的，到达它所能最远达到的点

这个点到mid的肯定都是满足的，都放入树状数组，然后找出<=first的数量

#include<bits/stdc++.h>
using namespace std;
int n;long long K;

struct data
{
    int h,v;
}edge[45];
int all[45];
long long ans;
struct node
{
    int h;long long w;
    bool operator < (const node & other)const 
    {
        return w<other.w;
    }
}s1[10010],s2[10010];
int len1,len2;

int c[45];
inline int lowbit(int x) {return x&(-x);}
void add(int a,int b)
{
    while(a<=n)
    {
        c[a]+=b;
        a+=lowbit(a);
    }
}
int sum(int a)
{
    int s=0;
    while(a)
    {
        s+=c[a];
        a-=lowbit(a);
    }
    return s;
}


int main()
{
    freopen("a.in","r",stdin);
//    freopen("san.out","w",stdout);
    scanf("%d%lld",&n,&K);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&edge[i].h,&edge[i].v);
        all[i]=edge[i].h;
    }
    sort(all,all+n);
    int mid=n>>1;
    int tot1=1<<mid,tot2=1<<(n-mid);
    for(int i=1;i<tot1;i++)
    {
        int pre=0;long long w=0;int flag=0;
        for(int j=0;j<mid;j++) 
        {
            if(i&(1<<j)) 
            {
                if(edge[j].h>=pre) pre=edge[j].h,w+=edge[j].v;
                else {flag=1;break;}
            }
        }
        if(flag) {continue;}
        if(w>=K) ans++;
        s1[len1++]=(node){pre,w};
    }
    for(int i=1;i<tot2;i++)
    {
        int first=0;int pre=0;long long w=0;int flag=0;
        for(int j=mid;j<n;j++) 
        {
            if(i&(1<<(j-mid)))
            {
                if(!first) first=edge[j].h;
                if(edge[j].h>=pre) pre=edge[j].h,w+=edge[j].v;
                else {flag=1;break;}
            }
        }
        if(flag) {continue;}
        if(w>=K) ans++;
        s2[len2++]=(node){first,w};
    }
    sort(s1,s1+len1);sort(s2,s2+len2);
    
    int pos=len1-1;
    for(int i=0;i<len2;i++)
    {
        while(pos>=0&&s1[pos].w+s2[i].w>=K) 
        {
            int t=lower_bound(all,all+n,s1[pos].h)-all+1;
        add(t,1);pos--;
        }
        int t=lower_bound(all,all+n,s2[i].h)-all+1;
        ans+=sum(t);
    }
    printf("%lld
",ans);
    return 0;
}

View Code