[离散化][前缀和][DP][二分]JZOJ 5873 小p的属性-白红宇

[离散化][前缀和][DP][二分]JZOJ 5873 小p的属性

阅读量：6648 次

发布时间：2019-06-25

本文共 1373 字，大约阅读时间需要 4 分钟。

Description

Input

Output

Sample Input

2 42 1 101 2 20

Sample Output

Data Constraint

分析

我们可以离散化之后处理二维前缀和（用二分找到位置）

然后DP方程显而易见

#include 
      
       #include 
       
        #include 
        
          using namespace std;typedef long long ll;const int N=1e3+10;ll x[N],y[N],a[N][3];ll s[N][N],f[N][N];int n,m; int cnt,nx,ny;int Bin_Search(int val,bool ot) {    int l=1,r=ot?ny:nx;    while (l<=r) {        int mid=l+r>>1;        if (ot?y[mid]==val:x[mid]==val) return mid;        if (ot?y[mid]
         
          
           m) continue;        a[++cnt][0]=a1;a[cnt][1]=a2;a[cnt][2]=a3;        x[cnt]=a1;y[cnt]=a2;    }    sort(x+1,x+cnt+1);sort(y+1,y+cnt+1);    nx=unique(x+1,x+cnt+1)-x-1;ny=unique(y+1,y+cnt+1)-y-1;    for (int i=1;i<=cnt;i++)        s[Bin_Search(a[i][0],0)][Bin_Search(a[i][1],1)]+=a[i][2];    for (int i=1;i<=nx;i++)        for (int j=1;j<=ny;j++)            s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];    for (int i=1;i<=nx;i++)        for (int j=1;j<=ny;j++)            f[i][j]=s[i][j]+max(f[i-1][j]+(x[i]-x[i-1]-1)*s[i-1][j],f[i][j-1]+(y[j]-y[j-1]-1)*s[i][j-1]);    ll lans=0;    for (int i=1;i<=nx;i++)        for (int j=1;j<=ny;j++)            lans=max(lans,f[i][j]+(m-x[i]-y[j])*s[i][j]);    printf("%lld",lans);    fclose(stdin);fclose(stdout);}