2020牛客ioi普及组 小y的游戏(二分技巧性dp)

小y的游戏

比赛的时候一眼$n=20$,状压?然而怪物的血量无法表示

于是想到了使用网络流,二分来判定,但是流量必须连续啊!!然后没辙了…

看了题解才知道是个$dp$题目

考虑$dp$,难点在于无法表示当前怪物的血量值,所以采用二分的办法判定

定义$dp[i][j][q][k]$表示打死了前$i$个怪兽,用了$j$次Ⅰ冲击,$j$次二冲击,$k$次三冲击

这是个$bool$数组,最后检验当$j,q,k$都小于等于二分值时是否可行即可

这样开,光是初始化就已经超时了…

但是可以用$dp$惯用的优化,就是让$dp$数组的值来表示状态

定义$dp[i][j][k]$为打死前$i$个怪兽用了$j$次一冲击,$k$次二冲击时花费最少的$三$冲击数

这样我们枚举当前用掉的一冲击二冲击

枚举本次打怪兽用的一冲击二冲击

傻瓜式转移即可

注意每个怪兽最多能被$mid$次冲击打到,因为一回合只能被打一次

#include <bits/stdc++.h> using namespace std; const int inf=1e9; int dp[21][241][241]; int n,a[22],t; bool isok(int mid) { for(int i=0;i<=n;i++) for(int j=0;j<=mid;j++) for(int q=0;q<=mid;q++) dp[i][j][q]=inf; dp[0][0][0]=0; for(int i=1;i<=n;i++) { for(int j=0;j<=mid;j++) for(int q=0;q<=mid;q++)//使用j次9攻击,q次3攻击 for(int nj=0;nj<=j;nj++) for(int nq=0;nq<=q&&nq<=max(0,(a[i]-nj*9)/3+1);nq++) { int x=a[i]-nj*9-nq*3; if( x<=0&&nj+nq>mid ) continue; if( x>0&&nj+nq+x>mid ) continue;//不能多于mid次攻击 if( x<=0 ) dp[i][j][q]=min( dp[i-1][j-nj][q-nq],dp[i][j][q] ); else if( x>0&&dp[i-1][j-nj][q-nq]+x<=mid ) dp[i][j][q]=min( dp[i-1][j-nj][q-nq]+x,dp[i][j][q] ); if( i==n&&dp[i][j][q]<=mid ) return true; } } return false; } int main() { cin >> t; while( t-- ) { cin >> n; int l=0,r=100,mid,ans=0; for(int i=1;i<=n;i++) cin >> a[i]; for(int i=1;i<=n;i++) if( a[i]<0 ) a[i]=0; while( r>=l ) { mid = l+r>>1; if( isok(mid) ) r=mid-1,ans=mid; else l=mid+1; } cout << ans << '\n'; } }