问题 H: Get Strong

在这里插入图片描述
数据很小，n = 20，这个应该可以直接搜索吧，我没试，我用的是折半搜索+二分+线段树维护区间最值，折半搜索就是先搜前10个，然后搜后10个，搜前10个的时候把每一个结果用一个pair<花费，权值>保存下来，然后按照花费排序，在第二次搜索的时候对于当前ww , vv需要的是一个前面搜索满足条件v<=m - vv的ww的最大值，然后就用一个线段树维护就行

#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3 , "Ofast" , "inline")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std ;
#define ios ios::sync_with_stdio(false) , cin.tie(0)
#define x first
#define y second
#define pb push_back
#define ls rt << 1
#define rs rt << 1 | 1
typedef long long ll ;
const double esp = 1e-6 , pi = acos(-1) ;
typedef pair PII ;
const int N = 1e6 + 10 , INF = 0x3f3f3f3f , mod = 1e9 + 7;
int ca = 0 ;
ll c[30][6] , w[30][6] , a[40] ;
ll n , m ;
PII b[N] ;
int cnt = 0 ;
ll maxn[N] ;
void up(int rt) {
  maxn[rt] = max(maxn[ls] , maxn[rs]) ;
  return ;
}
void build(int rt , int l , int r) {
  if(l == r) {
    maxn[rt] = b[l].y ;
    return ;
  }
  int mid = l + r >> 1 ;
  build(ls , l , mid) ;
  build(rs , mid + 1 , r) ;
  up(rt) ;
  return ;
}
ll ask(int rt , int l , int r , int ql , int qr) {
  if(ql <= l && r <= qr ) {
    return maxn[rt] ;
  }
  ll ans = -1e18 ;
  int mid = l + r >> 1;
  if(ql <= mid) ans = max(ans , ask(ls , l , mid , ql , qr)) ;
  if(qr > mid) ans = max(ans , ask(rs , mid + 1 , r , ql , qr)) ;
  return ans ;
}
void dfs(int u , ll ww , ll vv) {
  if(u == n / 2 + 1) {
    b[++ cnt] = {vv , ww} ;
    return ;
  }
  for(int i = 0 ;i <= a[u] ;i ++ )
    if(vv + c[u][i] <= m)
      dfs(u +1 , ww + w[u][i] , vv + c[u][i]) ;
  return ;
}
ll ans = 0 ;
void dfs1(int u , ll ww , ll vv) {
  if(u == n + 1) {
    ll t ;
    int l = 1 , r = cnt ;
    while(l <= r) {
       int mid = l + r >> 1 ;
       if(b[mid].x <= m - vv) l = mid + 1 , t = mid ;
       else r = mid - 1;
    }
 
    if(t >= 1)
     {
       ll res = ask(1 , 1 , cnt , 1 , t) ;
       ans = max(ans , ww + res) ;
     }
    return ;
  }
  for(int i = 0 ;i <= a[u] ;i ++ )
    if(vv + c[u][i] <= m)
      dfs1(u +1 , ww + w[u][i] , vv + c[u][i]) ;
  return ;
}
int work()
{
  cin >> n >> m ;
  cnt = 0 ;
  for(int i = 1; i <= n ;i ++ ) {
    ll ww , vv , k ;
    cin >> a[i] ;
    for(int j = 1; j <= a[i] ;j ++ ) {
      cin >> ww >> vv ;
      w[i][j] = w[i][j - 1] + ww ;
      c[i][j] = c[i][j - 1] + vv ;
    }
  }
  ans = 0 ;
  dfs(1 , 0 , 0) ;
  sort(b + 1 , b + cnt + 1) ;
  build(1 , 1 , cnt) ;
  dfs1(n / 2 + 1 , 0 , 0) ;
  printf("Case #%d: %lld\n" , ++ ca , ans) ;
  return 0 ;
}
int main()
{
  //   freopen("C://Users//spnooyseed//Desktop//in.txt" , "r" , stdin) ;
  //   freopen("C://Users//spnooyseed//Desktop//out.txt" , "w" , stdout) ;
  int n ;
  cin >> n ;
  while(n --)
  work() ;
  return 0 ;
}
/*
*/
upc线段树折半搜索

相关

#直径，线段树#51nod 1766 树上的最远点对

「NOI2020」命运（树形DP+线段树合并）

线段树学习笔记 1

关于 线段树 的一些认识

线段树

[NOI2015]软件包管理器（巧用线段树）

P6242 【模板】线段树 3

P5494 【模板】线段树分裂

CF1557D Ezzat and Grid（线段树）

setUp()、tearDown()和setUpClass()、tearDownClass()之间的区别

cf739 C. Alyona and towers（线段树）

可持久化线段树

标签