[Supplementary Question Diary] [2022 Hangzhou Electric Summer School Multi-School 3] B-Boss Rush

Pro

https://acm.hdu.edu.cn/showproblem.php?pid=7163

Sol

This question didn't end thereA掉.Mainly because I'm too lazyBecause after reading the idea at that time, I wrote down what I thought was the correct solution,It also took several hours to find out how and how I wrote itstd的区别在哪,Therefore there is no further comparisonstd写一遍,Instead, spend that part of your time researching the idea and why it's wrong.

I don't think I understand the meaning of this question,I also slowly understood the idea of ​​the questioner while writing and adjusting ,But monotonicity is still easy to see,So this question is a two-point answer.二分在xThe highest damage that can be hit in a frame,然后与HCompare whether the condition is met.

The problem is dichotomyjudge(check)函数怎么写：正确的做法为：因为最多只有18个技能,Therefore consider similar pressuresdp的方法,用$S$Decimal numbers indicate status,$f[S]$Indicates the maximum damage that can be dealt in this state,So when enumerating$S$时,It can be done by judging whether the skill is in this state$O(1)$的转移,The specific implementation method is as followsstd.Therefore, it can be obtained by the cumulative calculation of the stateTCan it be played under the frameH的伤害,It can also be judgedTWhether the frame meets the condition.

And a wrong spelling is ：No state transitions are made,for each state of the enumeration$S$Both recalculate the maximum damage that can be played,So as to determine whether it can be playedH.But the recalculation method is wrong,It is not possible to calculate the corresponding state in a very short time$S$中为1Whether the skills corresponding to the subscripts need to be completed.pressuredpThe writing method can avoid this problem,through the accumulation of states,The one that reaches the current state is the optimal state,Just need to consider whether the current skills are all finished.

Below is elegantstd.

Code

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=18,M=100005;
int Case,n,i,j,S,t[N],d[N],l,r,ans,mid,sum[(1<<N)+1];
ll hp,f[(1<<N)+1],dmg[N][M];
inline void up(ll&a,ll b){
    a<b?(a=b):0;}
bool check(int T){
    
  int S,i;
  for(S=0;S<1<<n;S++)f[S]=-1;
  f[0]=0;
  for(S=0;S<1<<n;S++){
    
    ll w=f[S];
    if(w<0)continue;
    if(w>=hp) {
    
      #ifdef DEBUG
      cout<<T<<' '<<S<<endl;
      #endif
      return 1;
    }
    int cur=sum[S];
    if(cur>T)continue;
    for(i=0;i<n;i++)if(!(S>>i&1)){
    
      if(cur+d[i]-1<=T)up(f[S|(1<<i)],w+dmg[i][d[i]-1]);
      else up(f[S|(1<<i)],w+dmg[i][T-cur]);
    }
  }
  return 0;
}
int main(){
    
  #ifdef DEBUG
  freopen("data.txt","r",stdin);
  #endif
  scanf("%d",&Case);
  while(Case--){
    
    scanf("%d%lld",&n,&hp);
    ans=-1,l=r=0;
    for(i=0;i<n;i++){
    
      scanf("%d%d",&t[i],&d[i]);
      r+=t[i]+d[i]-1;
      for(j=0;j<d[i];j++)scanf("%lld",&dmg[i][j]);
      for(j=1;j<d[i];j++)dmg[i][j]+=dmg[i][j-1];
    }
    for(S=1;S<1<<n;S++)sum[S]=sum[S-(S&-S)]+t[__builtin_ctz(S&-S)];
    while(l<=r){
    
      mid=(l+r)>>1;
      if(check(mid))r=(ans=mid)-1;else l=mid+1;
    }
    printf("%d\n",ans);
  }
}