【upc】2020年秋季组队训练赛第十四场 Get Strong | 折半搜索、二分

题目描述

WNJXYK and DIDIDI are friends. They are thinking about getting strong all the time.
They are playing a very hard online game and they can’t defeat any monster in this game now. If they can’t defeat monsters, they will not get EXP and will not get strong forever. They finally found that the only way for them to get strong is to upgrade their equipment with their limited coins. Each equipment can be upgrade many times with paying some money. And of course, they will get power from each upgrade.
They have N equipment in total and each equipment can be upgrade for Ki times. At first, equipment are all in Level 0. If you upgrade the ith equipment from Level j-1 to Level j, you will pay Cij coins and get Wij power. They have M coins in total and they want to know the most power they can get with these coins.

输入

The first line of input contains a positive integer T telling you there are T test cases followed.
In each Test Case, there is two positive integers N,M in the first line indicates that there are N equipment and M coins.
The following N Lines, there is a positive integer Ki at first indicates that the ith equipment can be upgrade Ki times. And there are 2Ki positive integers followed Wij,Cij.

输出

You need to output one line for each Test Case. “Case #X: Y” means the max power they can get in Xth Test Case is Y.

样例输入 Copy

1
3 5
1 1 1
2 1 1 5 4
1 5 3

样例输出 Copy

Case #1: 7

提示

Tips:1≤T≤10,1≤N≤20,0≤M≤1e9,0≤Ki≤4,1≤Cij,Wij≤1e9

In this Sample, they can upgrade their equipment like this and this is the only for them to get 7 power with 5 coins.  

题目大意：

给出一棵技能树，学到技能之后会获得权值 和 损失硬币

问在硬币<=M的情况下获得最大权值是多少？

题目思路：

首先可以把它分解为一个分组背包问题

但是由于m太大了，所以不能直接跑背包问题

n的范围是20，所以考虑折半搜索

先将n<=10的情况跑完，之后跑另一半找到在前面情况M-w的最大权值即可

Code:

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef  long long ll;
typedef unsigned long long ull;
const ll INF= 1e18;
const int maxn = 5e6;
const int mod= 998244353;
inline bool read(ll &num)
{char in;bool IsN=false;
    in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
struct node{
    ll w,v;
    bool friend operator<(node a,node b){
        return a.w < b.w;
    }
}a[maxn];
ll c[50],qw[50][10],qv[50][10];
int cnta,cntb;
ll mx[maxn];
ll ans = -INF;
void dfs1(int s,int t,ll w,ll v){
    if(s == t+1){
        a[++cnta] = node{w,v};
        ans = max(ans,v);
        return;
    }
    for(int k=1;k<=c[s];k++){
        if(w+qw[s][k]>m) continue;
        dfs1(s+1,t,w+qw[s][k],v+qv[s][k]);
    }
    dfs1(s+1,t,w,v);
}
int BiarySearch(ll tempw){
    int l = 1,r = cnta;
    int ans = -1;
    while(l<=r){
        int mid = (l+r)/2;
        if(a[mid].w <= tempw){
            l = mid+1;
            ans = mid;
        } else r = mid-1;
    }return ans;
}
void dfs2(int s,int t,ll w,ll v){
    if(s == t+1){
        ll tempw = m-w;
        int st = BiarySearch(tempw);
        if(~st) ans = max(ans,v+mx[st]);
        ans = max(ans,v);
        return;
    }
    for(int k=1;k<=c[s];k++){
        if(w+qw[s][k]>m) continue;
        dfs2(s+1,t,w+qw[s][k],v+qv[s][k]);
    }
    dfs2(s+1,t,w,v);
}
int main(){
    int cas = 0;
    int T;scanf("%d",&T);
    while(T--){
        cnta = cntb = 0;
        read(n);read(m);
        for(int i=1;i<=n;i++){
            read(c[i]);
            qw[i][0] = qv[i][0] = 0;
            for(int k=1;k<=c[i];k++){
                read(qv[i][k]);
                qv[i][k] += qv[i][k-1];
                read(qw[i][k]);
                qw[i][k] += qw[i][k-1];
            }
        }
        ans = -INF;
        dfs1(1,n/2,0,0);
        sort(a+1,a+1+cnta);
        mx[0] = -INF;
        for(int i=1;i<=cnta;i++) mx[i] = max(mx[i-1],a[i].v);
        dfs2(n/2+1,n,0,0);
        printf("Case #%d: %lld\n",++cas,ans);
    }
    return 0;
}
/***
 
***/