[SCOI2007]组队 差分

题面:[SCOI2007]组队

题解:

  一开始固定H然后找性质找了很久也没有找到任何有用的东西。。。。。。

  然后大佬告诉我一个神奇的方法。。。

  首先我们化一波式子:

  设$H$表示高度的最小值,$V$表示速度的最小值

  $$A(h[i] - H) - B(v[i] - V) \le C$$
  $$Ah[i] - AH + Bv[i] - BV \le C$$  

  如果我们枚举$h[i]$,那么$h[i]$就可以被当做一个常量,于是我们把常量都放在一起。
  设$$S_{i} = Ah[i] - AH - C$$
  则$$S_{i} + BV[i] - BV \le 0$$
  $$S_{i} + BV[i] <= BV$$
  $$\frac{S_{i}}{B} + V[i] \le V \le V[i]$$

  最后那个$\le V[i]$是因为V是最小值.

  于是我们可以发现,在固定H的情况下,对于任意一个V[i],它可以对在$[\frac{S_{i}}{B} + V[i], V[i]]$之间的V产生贡献。

  于是对于每个固定的H,我们的最大答案就看V最大能被多少个点产生贡献。

  差分维护即可

 #include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 5500
#define ac 101000
#define LL long long int n, ans, maxn, d[ac];
int A, B, C; struct node{
int h, v;
friend bool operator < (const node &a, const node &b){return a.h < b.h;}
}s[AC]; inline int read()
{
int x = ;char c = getchar();
while(c > '' || c < '') c = getchar();
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x;
} inline void upmax(int &a, int b){
if(b > a) a = b;
} inline void pre()
{
n = read(), A = read(), B = read(), C = read();
for(R i = ; i <= n; i ++)
{
s[i].h = read(), s[i].v = read();
upmax(maxn, s[i].v);
}
sort(s + , s + n + );
} void work()
{
for(R i = ; i <= n; i ++)//枚举minh
{
int H = s[i].h, all = H * A;
for(R j = i; j <= n; j ++)//在h符合条件的点当中选点来更新minv
{
int l = (s[j].h * A - all - C) / B + s[j].v, r = s[j].v;
if(l <= ) l = ;
if(l > r) continue;
++ d[l], -- d[r + ];
}
int tmp = ;
for(R j = ; j <= maxn; j ++)
tmp += d[j], upmax(ans, tmp), d[j] = ;
}
printf("%d\n", ans);
} int main()
{
freopen("in.in", "r", stdin);
pre();
work();
fclose(stdin);
return ;
}

  不知道为什么卡不过大佬QAQ。。。

上一篇:Spark SQL includes a cost-based optimizer, columnar storage and code generation to make queries fast.


下一篇:Android数据绑定:为混淆的AAR生成了错误的BR类