2022 Hangzhou Electric Power Multi-School Session 3 Question B Boss Rush

题目链接

Boss Rush

题目大意

给了我们一个Boss的血量,then gave us$n$个技能,Each skill has a casting time and a casting process time,Inflicts one continuous damage,The question asks when we can finish it soonestBoss?

题解

考虑二分答案,Then we need to make a judgment$mid$时间时,What is the maximum damage that can be done,如果大于等于Boss的血量,那么返回true,否则返回false.When we calculate max damage,Consider the use of shape pressureDP,$f[i]$中的$i$表示一个状态——哪一位为1It represents what skills have been used.The specific state transition can be seen in the code

代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
#define x first
#define y second
#define int long long
#define endl '\n' 
const int inf = 1e9 + 10;
const int maxn = 100010, M = 2000010;
const int mod = 1e9 + 7;
typedef pair<int,int> PII;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
int n, H;
int d[20][maxn], s[20][maxn];
int t[20], len[20];
int f[maxn * 3];
bool check(int mid)
{
    
    memset(f, -1, sizeof f);
    f[0] = 0;
    for(int i = 0; i < 1 << n; i ++){
    
        int time = 0;
        for(int j = 0; j < n; j ++){
    
            if(i >> j & 1) time += t[j];
        }
        if(time > mid) continue;
        for(int j = 0; j < n; j ++){
    
            if(i >> j & 1) continue;
            f[i | 1 << j] = max(f[i | 1 << j], f[i] + s[j][min(len[j], mid - time)]);
            if(f[i | 1 << j] >= H) return true;
        }
    }
    return false;
}
signed main()
{
    
    IOS;
    int T; cin >> T;
    while(T --)
    {
    
        cin >> n >> H;
        int l = 0, r = 0;
        for(int i = 0; i < n; i ++){
    
            cin >> t[i] >> len[i];
            r += max(t[i], len[i]);
            for(int j = 1; j <= len[i]; j ++) cin >> d[i][j];
            for(int j = 1; j <= len[i]; j ++) s[i][j] = s[i][j - 1] + d[i][j];
        }
        while(l < r){
    
            int mid = l + r >> 1;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        if(!check(l)) cout << -1 << endl;
        else cout << l - 1 << endl;
    }    
    return 0;
}