许嵩做的网站,申请园区网站建设经费的请示,wordpress哪个版本php,物流公司网站建设方案正题
题目链接:https://www.luogu.com.cn/problem/P7097 题目大意
有两个人在打游戏#xff0c;开始时每个人有个初始伤害xxx和delay值ddd。
有mmm种道具#xff0c;每个道具一个回合只能用一次#xff0c;可以使当前回合玩家伤害初始伤害的ki10000\frac{k_i}{10000}1000…正题
题目链接:https://www.luogu.com.cn/problem/P7097 题目大意
有两个人在打游戏开始时每个人有个初始伤害xxx和delay值ddd。
有mmm种道具每个道具一个回合只能用一次可以使当前回合玩家伤害初始伤害的ki10000\frac{k_i}{10000}10000ki倍数并增加该玩家delay值pip_ipi。每个回合delaydelaydelay值小的人攻击相同就第一个人要求delaydelaydelay值差值始终不超过100100100回合结束时操作的玩家会增加www点delay值。
求双方都最大化自己伤害减去对方伤害的情况下求nnn个回合后的伤害差。
1≤n≤103,1≤m≤105,1≤w,pi,ki≤1001\leq n\leq 10^3,1\leq m\leq 10^5,1\leq w,p_i,k_i\leq 1001≤n≤103,1≤m≤105,1≤w,pi,ki≤100 解题思路
对于这题我的评价是歌很好听题出的很好 下次不要再出了 就是题面有点长。
实际上还是很简单的首先道具每个回合是独立的我们可以先处理出数组fif_ifi表示iii点delaydelaydelay值会最多增加多少伤害用背包就好了。
然后剩下的因为delaydelaydelay差始终不超过100100100点设gi,jg_{i,j}gi,j表示第iii个回合delaydelaydelay差为jjj时的情况然后根据jjj倒着转移就好了。
除夕快乐。
时间复杂度O(100m1002n)O(100m100^2n)O(100m1002n) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e310,M1e510;
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 i1;im;i)scanf(%lld,k[i]);for(ll i1;im;i)scanf(%lld,p[i]);scanf(%lld%lld%lld%lld,xa,xb,da,db);for(ll i1;i200;i)f[i]-1e9;for(ll i1;im;i)for(ll j200;jp[i];j--)if(f[j-p[i]]!-1e9)f[j]max(f[j],f[j-p[i]]k[i]);for(ll i1;in;i)for(ll j0;j200;j){if(j100){g[i][j]-1e18;for(ll kjd;k200;k)if(f[k-j-d]!-1e9)g[i][j]max(g[i][j],g[i-1][k]xaxa/100000ll*f[k-j-d]);}else{g[i][j]1e18;for(ll k0;kj-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-db100]);return 0;
}
