bzoj4700 适者 CDQ分治+斜率优化毒瘤题

本文主要是介绍bzoj4700 适者 CDQ分治+斜率优化毒瘤题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：传送门

对于每个敌方的人形兵器，记录一个$B$，表示多少次能够打死这个人形兵器。
易知$B_i=\lceil \frac{D_i}{ATK}\rceil$。
首先考虑没有秒杀的情况：
显然应该按照某个顺序打死所有人形兵器（不可能打人形兵器A打到一半突然开始打B），所以考虑什么时候交换人形兵器$i,i+1$会使得结果更优：
发现交换$i,i+1$不会对$i$左边和$i+1$右边对答案的贡献有影响（这些人形兵器的攻击次数不变），所以只用考虑$i,i+1$两个人形兵器对答案的影响。
当$i$在前，$i+1$在后时，这两个人形兵器对答案的影响是：$(A[i]+A[i+1])\ast B[i]+A[i+1]\ast B[i+1]$
当$i+1$在前，$i$在后时，这两个人形兵器对答案的影响是：$(A[i]+A[i+1])\ast B[i+1]+A[i]\ast B[i]$
所以当$(A[i]+A[i+1])\ast B[i]+A[i+1]\ast B[i+1]>(A[i]+A[i+1])\ast B[i+1]+A[i]\ast B[i]$时，交换$i,i+1$会使答案更优qwq。
大莉化简一波，发现变成了$\frac{B[i]}{A[i]}>\frac{B[i+1]}{A[i+1]}$。
因此按照$\frac{B[i]}{A[i]}$从小到大排序（实际操作时我把cmp函数写成了乘法的形式，但本质上一样）
然后这个顺序就是打人形兵器的顺序qwq。

然后再考虑有秒杀的情况：
这里发现秒杀了一个人形兵器，其他兵器的相对顺序是不变的（因为$\frac{B[i]}{A[i]}$没有变qwq）
所以只用计算秒杀一个人形兵器对答案的影响：
这里令$sumt$表示攻击力的后缀和，$sumb$表示打死人形兵器所需次数的前缀和。
（注意$sumb[0]=-1$，因为你先攻击qwq）
如果什么都不秒杀，那么答案为$\Sigma {}_{i=1}^n(A[i]\ast sumb[i])$
假设第一次秒杀了$i$，
那么$i$号人形兵器会少造成$sumb[i]\ast A[i]$的伤害，
$i$之后的人形兵器会少造成$sumt[i+1]\ast B[i]$的伤害。
假设第二次秒杀了$j$（$i<j$），
那么$j$号人形兵器会少造成$(sumb[j]-B[i])\ast A[j]$的伤害，
$j$之后的人形兵器会少造成$sumt[j+1]\ast B[j]$的伤害。
那么秒杀$i,j$会让答案减少$sumb[i]\ast A[i]+sumt[i+1]\ast B[i]+(sumb[j]-B[i])\ast A[j]+sumt[j+1]\ast B[j]$。
动态规划，让$dp[i]$表示前$i$个人形兵器中秒杀$i$和另一个人形兵器能减少的伤害的最大值。
那么$dp[i]=$上面那一坨qwq。
$O(n^2)$显然跑不过去，把括号展开，移项，乱搞一波得到：
$A[j]\ast B[i]+dp[j]+常数=sumb[i]\ast A[i]+sumb[i+1]\ast B[i]$
然后硬上CDQ分治+斜率优化QAQ

毒瘤代码

#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<math.h>
#define re register int
using namespace std;
typedef long long ll;
int read() {re x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-')	f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=10*x+ch-'0';ch=getchar();}return x*f;
}
inline char GetChar() {char ch=getchar();while(ch!='Q' && ch!='B')	ch=getchar();return ch;
}
const int Size=300001;
namespace I_Love {ll n,ATK,sumb[Size],sumt[Size];
struct Tank {ll A,D,B,val;
} a[Size];
ll val[Size];
inline bool cmp(Tank x,Tank y) {return x.B*y.A<y.B*x.A;
}
struct node {ll x,y;int id;
} w[Size],tmp[Size],Queue[Size];
ll dp[Size];
void Divide(int l,int r) {int mid=(l+r)>>1;int ptrl=l-1,ptrr=mid;for(re i=l; i<=r; i++) {if(w[i].id<=mid) {tmp[++ptrl]=w[i];} else {tmp[++ptrr]=w[i];}}for(re i=l; i<=r; i++) {w[i]=tmp[i];}
}
inline bool operator < (node a,node b) {if(a.x!=b.x)	return a.x<b.x;return a.y>b.y;
}
void Merge(int l,int r) {int mid=(l+r)>>1;int ptrl=l,ptrr=mid+1,tot=l-1;while(ptrl<=mid && ptrr<=r) {if(w[ptrl]<w[ptrr]) {tmp[++tot]=w[ptrl++];} else {tmp[++tot]=w[ptrr++];}}while(ptrl<=mid)	tmp[++tot]=w[ptrl++];while(ptrr<=r)		tmp[++tot]=w[ptrr++];for(re i=l; i<=r; i++) {w[i]=tmp[i];}
}
inline double slope(node mhy,node wqt) {if(mhy.x==wqt.x)	return -1e20;	//防止除0 return (double)(wqt.y-mhy.y)/(wqt.x-mhy.x);
}
void CDQ_Divide(int l,int r) {if(l==r) {w[l].y=sumb[l]*a[l].A+sumt[l+1]*a[l].B;return;}int mid=(l+r)>>1;Divide(l,r);CDQ_Divide(l,mid);int hd=1,tl=0;for(re i=l; i<=mid; i++) {while(hd<tl && slope(Queue[tl-1],Queue[tl])<slope(Queue[tl],w[i]))	tl--;Queue[++tl]=w[i];}for(re i=mid+1; i<=r; i++) {while(hd<tl && slope(Queue[hd],Queue[hd+1])>a[w[i].id].A)	hd++;int x=w[i].id,y=Queue[hd].id;//dp:reduce damagedp[x]=max(dp[x],(ll)val[x]+(ll)val[y]-a[x].A*a[y].B);}CDQ_Divide(mid+1,r);Merge(l,r);
}
inline bool comp(node mhy,node wqt) {
//	if(mhy.x!=wqt.x)	return mhy.x<wqt.x;
//	return mhy.id<wqt.id;return a[mhy.id].A<a[wqt.id].A;
}
void Kutori() {n=read();ATK=read();for(re i=1; i<=n; i++) {a[i].A=read();a[i].D=read();a[i].B=ceil((double)a[i].D/ATK);}sumb[0]=-1;sort(a+1,a+1+n,cmp);for(re i=1; i<=n; i++)	sumb[i]=sumb[i-1]+a[i].B;for(re i=n; i>0; i--)	sumt[i]=sumt[i+1]+a[i].A;ll tot=0;for(re i=1; i<=n; i++) {w[i].x=a[i].B;w[i].id=i;tot+=a[i].A*sumb[i];w[i].y=val[i]=sumt[i+1]*a[i].B+a[i].A*sumb[i];}sort(w+1,w+1+n,comp);CDQ_Divide(1,n);
//	printf("I love Furukawa Nagisa---%d\n",tot);ll ans=tot;for(re i=1; i<=n; i++) {ll now=tot-dp[i];if(now<ans)	ans=now;}printf("%lld",ans);
}}
int main() {I_Love::Kutori();return 0;
}
/*
4 1
6889 314
8320 8789
478 4833
3186 1386
*/

这篇关于bzoj4700 适者 CDQ分治+斜率优化毒瘤题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---