題目鏈接：ssss - Virtual Judge

?

樣例輸入：

3 1 100 5 3 50 60 70 2 100 2 3 40 40 100 100 2 20 5 1 1000 1 1 999

樣例輸出：

1 2 -1

題意：多組樣例，每組樣例先給一個n和H，分別代表技能數(shù)和boss血量，接下來對于每個技能都有兩行輸入，第一行給出兩個數(shù)分別代表技能使用時間t[i]和技能持續(xù)時間len[i]，接下來一行給出len[i]個數(shù)，分別代表每一秒可以對Boss造成的傷害，我們使用一個技能后，在使用該技能期間會對Boss造成傷害，但是無法使用其他技能，問我們殺死Boss所需要的最小時間，如果無法殺死Boss就直接輸出-1.

分析：看了一下數(shù)據(jù)范圍，發(fā)現(xiàn)技能最多只有18個，然后就想到了用狀壓去做，我們可以二分時間，設(shè)置二分邊界分別為0，1e18，那么二分復(fù)雜度就是log(1e18)，f[st]表示技能使用狀態(tài)為st的條件下在某段時間內(nèi)最多造成的傷害（某段時間是二分值），這個更新過程是n*2^n，所以總的復(fù)雜度就是O（log(1e18)*n*2^n）。

下面來看一下如何進(jìn)行動態(tài)轉(zhuǎn)移。

我們要判斷是否能在T時間內(nèi)打敗Boss，那么我們的f[st]就表示技能使用狀態(tài)為st的條件下在時間T內(nèi)對Boss最多造成的傷害值，我們需要從1~（1<<n）枚舉技能使用狀態(tài)st，我們需要預(yù)處理一下到達(dá)任意狀態(tài)所需要的時間，假如當(dāng)前狀態(tài)是st，如果當(dāng)前狀態(tài)的傷害值大于Boss血量H，那么我們就直接返回true，如果當(dāng)前狀態(tài)所需要的時間大于T，那么我們就沒必要繼續(xù)更新當(dāng)前狀態(tài)的下一個狀態(tài)了，因為利用當(dāng)前狀態(tài)去更新的下一個狀態(tài)所使用的技能會更多，花費時間也會更多，沒有意義。我們更新狀態(tài)是枚舉當(dāng)前狀態(tài)下還沒有使用的技能，比如是技能i，如果使用第i個技能后總時間依舊沒有到達(dá)T，那么我們就把當(dāng)前技能的傷害值全部計入f[st|(1<<i)]，如果要是使用第i個技能后總時間超過了T，那么由于我們的技能傷害從開始使用時就已經(jīng)開始計算，所以我們只需要計算在T時間前的這一段時間所造成的傷害即可。注意我們利用的是技能使用狀態(tài)達(dá)到st所需要的時間，也就是說技能釋放的時間和而不是技能持續(xù)時間和，一定要搞清楚兩者之間的關(guān)系，按照這個更新過程去更新答案，如果更新到最后也沒有一個狀態(tài)st使得f[st]>=H，那么就返回false.

下面是代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<map> #include<queue> #include<vector> #include<cmath> using namespace std; const int N=1e5+10; typedef long long ll; ll sum[20][N];//sum[i][j]表示第i個技能前j秒可以造成的傷害 ll H,n,t[20],len[20]; ll f[1<<20];//f[st]表示狀態(tài)st在某段時間內(nèi)最多造成的傷害（某段時間是二分值） ll sumt[1<<20];//sumt[st]表示觸發(fā)技能在狀態(tài)st下最少需要的觸發(fā)時間 bool check(ll T) {ll ans=0;for(int i=1;i<1<<n;i++) f[i]=-1;f[0]=0;for(int st=0;st<1<<n;st++){ll w=f[st]; if(w==-1) continue;//說明當(dāng)前狀態(tài)st在t時間內(nèi)無法完全觸發(fā)if(w>=H) return true;//說明狀態(tài)st下在t時間內(nèi)造成的傷害已經(jīng)可以殺死怪物 if(sumt[st]>T) continue;for(int i=0;i<n;i++)//枚舉還未觸發(fā)的技能 {if(st>>i&1) continue;//該技能已觸發(fā)if(sumt[st]+len[i]-1<=T) f[st|(1<<i)]=max(f[st|(1<<i)],f[st]+sum[i][len[i]]);else f[st|(1<<i)]=max(f[st|(1<<i)],f[st]+sum[i][T-sumt[st]+1]);}}return false; } int main() {int T;cin>>T;while(T--){scanf("%lld%lld",&n,&H);for(int i=0;i<n;i++){scanf("%lld%lld",&t[i],&len[i]);for(int j=1;j<=len[i];j++){scanf("%lld",&sum[i][j]);sum[i][j]+=sum[i][j-1];}}for(int st=1;st<1<<n;st++)//預(yù)處理觸發(fā)技能在狀態(tài)st下最少需要的觸發(fā)時間{sumt[st]=0;//別忘了初始化 for(int i=0;i<n;i++)if(st>>i&1) sumt[st]+=t[i];}ll l=0,r=1e18;while(l<r){ll mid=l+r>>1;if(check(mid)) r=mid;else l=mid+1;}if(check(l)) printf("%lld\n",l);else puts("-1");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的（2022杭电多校三）1002-Boss Rush（状压DP+二分）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。