正題

題目鏈接:https://www.luogu.com.cn/problem/P7097

---

題目大意

有兩個(gè)人在打游戲，開始時(shí)每個(gè)人有個(gè)初始傷害$x$和delay值$d$。

有$m$種道具，每個(gè)道具一個(gè)回合只能用一次，可以使當(dāng)前回合玩家傷害初始傷害的$\frac{k_i}{10000}$倍數(shù)，并增加該玩家delay值$p_i$。每個(gè)回合$delay$值小的人攻擊（相同就第一個(gè)人），要求$delay$值差值始終不超過$100$，回合結(jié)束時(shí)操作的玩家會(huì)增加$w$點(diǎn)delay值。

求雙方都最大化自己傷害減去對(duì)方傷害的情況下求$n$個(gè)回合后的傷害差。

$1\le n\le 10^3,1\le m\le 10^5,1\le w,p_i,k_i\le 100$

---

解題思路

對(duì)于這題我的評(píng)價(jià)是，歌很好聽，題出的很好 下次不要再出了 ，就是題面有點(diǎn)長。

實(shí)際上還是很簡單的，首先道具每個(gè)回合是獨(dú)立的，我們可以先處理出數(shù)組$f_i$表示$i$點(diǎn)$delay$值會(huì)最多增加多少傷害，用背包就好了。

然后剩下的因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$delay$差始終不超過$100$點(diǎn)，設(shè)$g_{i,j}$表示第$i$個(gè)回合，$delay$差為$j$時(shí)的情況，然后根據(jù)$j$倒著轉(zhuǎn)移就好了。

除夕快樂。

時(shí)間復(fù)雜度：$O(100m+100^{2}n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e3+10,M=1e5+10; ll T,n,m,d,xa,xb,da,db; ll k[M],p[M],f[210],g[N][210]; signed main() {scanf("%lld",&T);scanf("%lld%lld%lld",&n,&m,&d);for(ll i=1;i<=m;i++)scanf("%lld",&k[i]);for(ll i=1;i<=m;i++)scanf("%lld",&p[i]);scanf("%lld%lld%lld%lld",&xa,&xb,&da,&db);for(ll i=1;i<=200;i++)f[i]=-1e9;for(ll i=1;i<=m;i++)for(ll j=200;j>=p[i];j--)if(f[j-p[i]]!=-1e9)f[j]=max(f[j],f[j-p[i]]+k[i]);for(ll i=1;i<=n;i++)for(ll j=0;j<=200;j++){if(j<=100){g[i][j]=-1e18;for(ll k=j+d;k<=200;k++)if(f[k-j-d]!=-1e9)g[i][j]=max(g[i][j],g[i-1][k]+xa+xa/100000ll*f[k-j-d]);}else{g[i][j]=1e18;for(ll k=0;k<=j-d;k++)if(f[j-k-d]!=-1e9)g[i][j]=min(g[i][j],g[i-1][k]-xb-xb/100000ll*f[j-k-d]);}}printf("%lld\n",g[n][da-db+100]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的P7097-[yLOI2020]牵丝戏【dp】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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