題目鏈接：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

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

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

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

我們要判斷是否能在T時(shí)間內(nèi)打敗Boss，那么我們的f[st]就表示技能使用狀態(tài)為st的條件下在時(shí)間T內(nèi)對(duì)Boss最多造成的傷害值，我們需要從1~（1<<n）枚舉技能使用狀態(tài)st，我們需要預(yù)處理一下到達(dá)任意狀態(tài)所需要的時(shí)間，假如當(dāng)前狀態(tài)是st，如果當(dāng)前狀態(tài)的傷害值大于Boss血量H，那么我們就直接返回true，如果當(dāng)前狀態(tài)所需要的時(shí)間大于T，那么我們就沒必要繼續(xù)更新當(dāng)前狀態(tài)的下一個(gè)狀態(tài)了，因?yàn)槔卯?dāng)前狀態(tài)去更新的下一個(gè)狀態(tài)所使用的技能會(huì)更多，花費(fèi)時(shí)間也會(huì)更多，沒有意義。我們更新狀態(tài)是枚舉當(dāng)前狀態(tài)下還沒有使用的技能，比如是技能i，如果使用第i個(gè)技能后總時(shí)間依舊沒有到達(dá)T，那么我們就把當(dāng)前技能的傷害值全部計(jì)入f[st|(1<<i)]，如果要是使用第i個(gè)技能后總時(shí)間超過(guò)了T，那么由于我們的技能傷害從開始使用時(shí)就已經(jīng)開始計(jì)算，所以我們只需要計(jì)算在T時(shí)間前的這一段時(shí)間所造成的傷害即可。注意我們利用的是技能使用狀態(tài)達(dá)到st所需要的時(shí)間，也就是說(shuō)技能釋放的時(shí)間和而不是技能持續(xù)時(shí)間和，一定要搞清楚兩者之間的關(guān)系，按照這個(gè)更新過(guò)程去更新答案，如果更新到最后也沒有一個(gè)狀態(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個(gè)技能前j秒可以造成的傷害 ll H,n,t[20],len[20]; ll f[1<<20];//f[st]表示狀態(tài)st在某段時(shí)間內(nèi)最多造成的傷害（某段時(shí)間是二分值） ll sumt[1<<20];//sumt[st]表示觸發(fā)技能在狀態(tài)st下最少需要的觸發(fā)時(shí)間 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;//說(shuō)明當(dāng)前狀態(tài)st在t時(shí)間內(nèi)無(wú)法完全觸發(fā)if(w>=H) return true;//說(shuō)明狀態(tài)st下在t時(shí)間內(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ā)時(shí)間{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+二分）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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