小y的游戏(二分技巧性dp)

比赛的时候一眼 $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<=(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';
    }
}