题解|【HNOI2017】大佬-dalao 搜索|dp

题面

??
文章图片

??
文章图片

解法

bfs+DP ：
??这道题的想法很妙，问了本校的很多大佬之后才搞懂。
??我们可以发现，刷题长自信值和回嘴/怼大佬是两个独立的过程，如果我们能够在保证自己的自信值 ≥0 的同时使得可以不用刷题的天数尽可能多，那么我们就可能打败大佬。
??所以我们设 f[i][j] 表示前i天，自信值为j时最多有多少天不用刷题， d[f][l] 变成讽刺能力为f，等级为l需要的最少天数，假设这个最大值为D，
??假设当前大佬的自信值为x， f[i][j] 的最大值为D，假设进行两次怼的操作，所需要的天数和造成的伤害分别为d1，f1，d2，f2
??那么当满足：D-d1-d2>=C-f1-f2时就可以怼死大佬（d1，f1，d2，f2可以为0）
??这样理解：怼两次大佬不能直接怼死了，必须要怼到刚刚好，即D>=d1+d2，C=f1+f2；或者说没有刚刚好，大佬还剩下C-f1-f2的自信值，自己还剩下D-d1-d2的天数，那么就可以还嘴把大佬搞死
??所以我们可以用DP求出f数组，用bfs求出d数组，求出来之后就可以解答。
??对于每一个大佬，我们把状态按照f排序，枚举其中一次怼的造作，用单调指针来扫另一次怼操作，记录另一次怼的最小值，如果发现满足等式那就可以直接输出1了。

复杂度

O（ n?mc+玄学+m?cnt ），玄学就是bfs的状态数，不是很多，cnt是合法的状态数

【题解|【HNOI2017】大佬-dalao】代码

#include #include #include #include #include #include #define Rint register int #define Lint long long int using namespace std; const int INF=0x3f3f3f3f; const int N=6010; struct node { int d,f; bool operator < (const node &a) const { return f220]; int a[N],w[N],c[N],q[N*220],F[N*220],L[N*220]; int n,m,mc,mx,D,cnt; int f[N][N]; map > d; void bfs() { int h=0,t=1; F[t]=1,L[t]=0,d[1][0]=q[t]=1; //赋初值，F为讽刺能力，L为等级 while( h=D )continue ; int x=F[h],y=L[h]; if( !d[x][y+1] ) { F[++t]=x,L[t]=y+1; d[x][y+1]=q[t]=tmp+1; } if( (Lint)x*(Lint)y<=1ll*mx && !d[x*y][y] ) { F[++t]=x*y,L[t]=y; d[x*y][y]=q[t]=tmp+1; } } p[++cnt]=(node){ 0,0 }; for(int i=1; i<=t; i++)p[++cnt]=(node){ q[i],F[i] }; sort( p+1,p+cnt+1 ); } bool judge(int x) { int j=1,v=INF; for(int i=cnt; i ; i--) { while( p[i].f+p[j].f<=x && i>j )v=min( v,p[j].d-p[j].f ),j++; if( D-x>=v+p[i].d-p[i].f )return 1; } return 0; } int main() { freopen("dalao.in","r",stdin); freopen("dalao.out","w",stdout); scanf("%d%d%d",&n,&m,&mc); for(int i=1; i<=n; i++)scanf("%d",&a[i]); for(int i=1; i<=n; i++)scanf("%d",&w[i]); for(int i=1; i<=m; i++) { scanf("%d",&c[i]); mx=max( mx,c[i] ); } memset( f,-1,sizeof f ); f[0][mc]=0; for(int i=1,x; i<=n; i++) for(int j=a[i]; j<=mc; j++) { f[i][j-a[i]]=max( f[i][j-a[i]],f[i-1][j]+1 ); x=min( mc,j-a[i]+w[i] ); f[i][x]=max( f[i][x],f[i-1][j] ); } for(int i=0; i<=n; i++)for(int j=0; j<=mc; j++)D=max( D,f[i][j] ); bfs(); for(int i=1; i<=m; i++) if( judge( c[i] ) )printf("1\n"); elseprintf("0\n"); return 0; }