[二分+DP]魔棒

希望更好的阅读效果？点这里

题目：

描述

有一个英雄，初始生命值是 $hp$hp（生命值无上限），在接下来的 $n$n （$n \le 500$n≤500）秒内，每秒会受到一次伤害，第 $i$i 秒受到的伤害值为 $a[i]$a[i]（$1 \le |a[i]| \le 1000$1≤∣a[i]∣≤1000）。这个英雄有一个道具"魔杖"，魔杖的初始能量为 $0$0 ，每受到 $1$1 次伤害，积攒 $1$1 点能量。在英雄受到伤害后，可以立即释放魔棒中的能量，恢复 $15 \times [能量点数]$15×[能量点数] 的生命值，且魔棒的点数清零。释放能量有施法间隔 $cd$cd（$cd$cd 是正整数），即相邻的两次释放的时间间隔至少有 $cd$cd 秒。任何时刻当 $hp \le 0$hp≤0 时视为死亡，问这个英雄存活下来的前提下，$cd$cd 的值最大可以是多少？注意，若 $a[i]$a[i] 为负，受到"伤害"后实际上生命值是增加的，魔棒仍然积攒能量。

输入

第一行一个整数 $T$T ，表示测试数据的组数。对于每组测试数据：
第 $1$1 行两个正整数 $n,hp$n,hp ，含义如题目所述。
第 $2$2 行 $n$n 个整数，分别是 $a[1] \sim a[n]$a[1]∼a[n] 。

输出

对每组测试数据输出一行包含一个数，即最大的 $cd$cd ，$cd$cd 是一个正整数。如果 $cd$cd 没有上限，输出"No upper bound."（不含双引号）；如果无论如何都不能存活，输出 $−1$−1 。

分析：

多组数据 $T \le 5$T≤5 与 $n \le 500$n≤500 是很小的，但是真的有那么容易吗？

设 $cd$cd 最大为 $x$x ，如果 $cd>x$cd>x 英雄不能存活，否则就能够存活。于是可以二分 $cd$cd 的值，如果 $1~n$1 n 秒 $hp>0$hp>0 ，则把 $mid$mid 调大。否则就调小。

像我这种蒟蒻差分约束系统显然是不会的，只会用DP写check函数。

设 $f[i][j][k]$f[i][j][k] 表示到第 $i$i 秒末，能量点数为 $j$j ，释放了 $k$k 次后还有的最大生命值。

初始化：$f[0][0][0]=hp$f[0][0][0]=hp 。

因为释放次数大于等于 $2$2 时需要知道间隔，所以k取 $0,1,2$0,1,2 三个值就行了。（$k=2$k=2 时表示释放次数 $\ge 2$≥2），对每个取值分类讨论：

• $k=0:$k=0:

  此时很明显 $j=i$j=i ，所以：

  $f[i][i][0]=f[i-1][i-1][0]-a[i]$f[i][i][0]=f[i−1][i−1][0]−a[i]

  注意要满足 $f[i-1][i-1][0]>a[i]$f[i−1][i−1][0]>a[i] ，表示能活到第 $i$i 秒。

• $k=1:$k=1:

  1. 在第 $i$i 秒末释放能量：

     $f[i][0][1]=f[i-1][i-1][0]-a[i]+i \times 15$f[i][0][1]=f[i−1][i−1][0]−a[i]+i×15

     这时也要满足 $f[i-1][i-1][0]>a[i]$f[i−1][i−1][0]>a[i] 。

  2. 在前面释放能量：

     $j$j 从 $1$1 到 $i-1$i−1 （因为已经释放过一次，所以 $j$j 不能等于 $i$i）：

     $f[i][j][1]=max \{f[i-1][j-1][1]-a[i] \}$f[i][j][1]=max{f[i−1][j−1][1]−a[i]}

     这时要满足 $f[i-1][j-1][1]>a[i]$f[i−1][j−1][1]>a[i] 。

• $k=2:$k=2:

  1. 前面释放过但第 $i$i 秒末没有释放：

     $f[i][j][2]=max \{f[i-1][j-1][2]-a[i] \}$f[i][j][2]=max{f[i−1][j−1][2]−a[i]}

     此时要满足 $f[i-1][j-1][2]>a[i]$f[i−1][j−1][2]>a[i] 。

  2. 第 $i$i 秒末释放的是第二次：

     $f[i][0][2]=max \{f[i][j][2],f[i-1][j-1][1]-a[i]+j \times 15 \}$f[i][0][2]=max{f[i][j][2],f[i−1][j−1][1]−a[i]+j×15}

     “$f[i-1][j-1][1]-a[i]+j \times 15$f[i−1][j−1][1]−a[i]+j×15”表示 $i-1$i−1 秒末，能量为 $j-1$j−1 时或在前面放过一次，此时要满足 $j \ge mid$j≥mid 并且 $f[i-1][j-1][1]>a[i]$f[i−1][j−1][1]>a[i] 。

  3. 第 $i$i 秒末释放第 $k$k 次（$k>2$k>2）：

     $f[i][0][2]=max \{f[i][j][2],f[i-1][j-1][2]-a[i]+j \times 15 \}$f[i][0][2]=max{f[i][j][2],f[i−1][j−1][2]−a[i]+j×15}

     这个式子表示 $i-1$i−1 秒末，能量为 $j-1$j−1 时或在前面放过多次，此时也要满足 $j \ge mid$j≥mid 且 $f[i-1][j-1][2]>a[i]$f[i−1][j−1][2]>a[i] 。

最后判断 $f[n][i][0],f[n][i][1],f[n][i][2]$f[n][i][0],f[n][i][1],f[n][i][2] ，只要有一个大于 $0$0 就行了。

代码：

#include <cstdio>
#include <cstring>
#define max(a,b) ((a)>(b)?(a):(b))
int t,n,hp,a[503],f[503][503][3];
bool check(int mid){
    memset(f,-0x3f,sizeof f);//多组数据一定要清空
    f[0][0][0]=hp;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=i;j++){
            //k=0:
            if(f[i-1][i-1][0]>a[i]) f[i][i][0]=f[i-1][i-1][0]-a[i];
            //k=1:
            if(f[i-1][i-1][0]>a[i])
                f[i][0][1]=f[i-1][i-1][0]-a[i]+i*15;
            if(j>=1&&f[i-1][j-1][1]>a[i])
                f[i][j][1]=max(f[i][j][1],f[i-1][j-1][1]-a[i]);
            //k=2:
            if(j>=1&&f[i-1][j-1][2]>a[i])
                f[i][j][2]=max(f[i][j][2],f[i-1][j-1][2]-a[i]);
            if(j>=mid&&f[i-1][j-1][1]>a[i])
                f[i][0][2]=max(f[i][j][2],f[i-1][j-1][1]-a[i]+j*15);
                //这里的f[i][j][2]可以换成f[0][2]，下同
            if(j>=mid&&f[i-1][j-1][2]>a[i])
                f[i][0][2]=max(f[i][j][2],f[i-1][j-1][2]-a[i]+j*15);
        }
    for(int i=0;i<=n;i++)
        if(f[n][i][0]>0||f[n][i][1]>0||f[n][i][2]>0) return 1;
        //判断，只要有一个>0就返回1
    return 0;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&hp);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        int l=0,r=n+1;//r=n+1是为了方便判断没有上界的情况
        while(l<=r){//二分模板
            int mid=l+r>>1;
            if(check(mid)) l=mid+1;
            else r=mid-1;
        }
        if(r==n+1) puts("No upper bound.");
        else printf("%d\n",l-1);
    }
    return 0;
}