【NOIP 2015シミュレーション11.2】おもしろいファミリー菜園

9264 ワード

Description
各位置に高さh,費用c,重みbを有するシーケンスが与えられる.位置を削除するコストと、位置を削除する費用を支払うことができます.次に、以下の条件を満たすすべての位置の重み値の収益を得ることができます.1:除去されていないj,j
Solution
明らかに、最後に選んだものの高さは上凸関数です.では、左/右からの増加の最大利益を表す2つの状態fとgを設定することができます.では
f[i]=maxjh[i]k=i−1c[k])+b[i]
gの転移は類似している.
では、これをO(N^3)O(N^2)といいます
最適化の方法を考える.a[h[j]]を各高さmaxの中の塊を表すとします.
では、iを終了すると、a[1]~a[h[i]-1]はc[i]を1つ減算する必要があります.
そしてf[i]をh[i]という位置に挿入する.
毎回答えはa[1]~a[h[i]]の最大値である.
Code

#include
#include
#include
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define N 100005
#define ll long long
using namespace std;
struct note {int v,w;}a[N];
bool cmp(note x,note y) {return x.v<y.v;}
int n,h[N],tot;
ll b[N],c[N],f[N],g[N],t[N*3],lazy[N*3],ans,cost;
void back(int v,ll z) {lazy[v]+=z;t[v]-=z;} 
void down(int v) {
    if (lazy[v]) {
        back(v*2,lazy[v]);back(v*2+1,lazy[v]);
        lazy[v]=0;
    }
}
void change(int v,int l,int r,int x,int y,ll z) {
    if (l==x&&r==y) {back(v,z);return;}
    int m=(l+r)/2;down(v);
    if (y<=m) change(v*2,l,m,x,y,z);
    else if (x>m) change(v*2+1,m+1,r,x,y,z);
    else change(v*2,l,m,x,m,z),change(v*2+1,m+1,r,m+1,y,z);
    t[v]=max(t[v*2],t[v*2+1]);
}
void insert(int v,int l,int r,int x,ll y) {
    if (l==r) {t[v]=max(t[v],y);return;}
    int m=(l+r)/2;down(v);
    if (x<=m) insert(v*2,l,m,x,y);
    else insert(v*2+1,m+1,r,x,y);
    t[v]=max(t[v*2],t[v*2+1]);
}
ll find(int v,int l,int r,int x,int y) {
    if (l==x&&r==y) return t[v];
    int m=(l+r)/2;down(v);
    if (y<=m) return find(v*2,l,m,x,y);
    else if (x>m) return find(v*2+1,m+1,r,x,y);
    else return max(find(v*2,l,m,x,m),find(v*2+1,m+1,r,m+1,y));
}
int main() {
    freopen("herbary.in","r",stdin);
    freopen("herbary.out","w",stdout);
    scanf("%d",&n);
    fo(i,1,n) scanf("%d%lld%lld",&a[i].v,&b[i],&c[i]),a[i].w=i;
    sort(a+1,a+n+1,cmp);a[0].v=-1;
    fo(i,1,n) {
        if (a[i].v!=a[i-1].v) tot++;
        h[a[i].w]=tot;
    }
    memset(t,128,sizeof(t));insert(1,0,tot,0,0);
    fo(i,1,n) {
        f[i]=find(1,0,tot,0,h[i])+b[i];
        change(1,0,tot,0,h[i],c[i]);insert(1,0,tot,h[i],f[i]);
    }
    memset(t,128,sizeof(t));insert(1,0,tot,0,0);
    fd(i,n,1) {
        g[i]=find(1,0,tot,0,h[i])+b[i];
        change(1,0,tot,0,h[i],c[i]);insert(1,0,tot,h[i],g[i]);
    }
    fo(i,1,n) ans=max(ans,f[i]+g[i]-b[i]);
    printf("%lld",ans);
}

統計メモ：期待値

順序ロジットモデル/プロビットモデルを理解する