題意：

題意

分析：

• 推柿子 ：

$A\times h?A\times mi{n}_h+B\times s?B\times mi{n}_s\le C$

我們發(fā)現(xiàn)有三個(gè)變量，所以最暴力的復(fù)雜度是$O(n^3)$的，那么我們考慮怎么優(yōu)化

好吧，我不看題解也不是很會(huì)優(yōu)化

我們將式子轉(zhuǎn)化一下，然后會(huì)發(fā)現(xiàn)對(duì)于每一個(gè)人，$mi{n}_h$固定時(shí)，能取到的合法$mi{n}_s$是連續(xù)的

$$\frac{A\times (h?mi{n}_h)?C}{B}+s\le mi{n}_v\le s$$

前面一個(gè)限制是由式子轉(zhuǎn)化得到的，后面的限制是題目要求，$mi{n}_s\le ?s$

對(duì)于區(qū)間加的操作直接差分一下

代碼：

#include<bits/stdc++.h>using namespace std;namespace zzc {const int maxn = 5005;long long h[maxn],s[maxn],num[10005],d[maxn];long long n,cnt=0,ans,a,b,c;void work(){ios::sync_with_stdio(false);cin>>n>>a>>b>>c;for(int i=1;i<=n;i++){cin>>h[i]>>s[i];d[i]=h[i];}sort(d+1,d+n+1);cnt=unique(d+1,d+n+1)-d-1;for(int i=1,l;i<=cnt;i++){memset(num,0,sizeof(num));for(int j=1;j<=n;j++){if(h[j]>=d[i]&&a*(h[j]-d[i])<=c){if(b==0) l=1;else l=max(1ll,s[j]-(c-a*(h[j]-d[i]))/b);num[l]++;num[s[j]+1]--;}}for(int j=1;j<=10000;j++) num[j]+=num[j-1];for(int j=1;j<=n;j++) ans=max(ans,num[s[j]]);}cout<<ans<<endl;}}int main() {zzc::work();return 0; }

總結(jié)

以上是生活随笔為你收集整理的P4165 [SCOI2007]组队 推柿子+差分的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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