BZOJ2131 免费的馅饼

2014.12.17 15:52 Wed| 5 visits oi_2015| 2015_刷题日常| Text

想起了曾经的考试题,明明想到了最简单的小DP的正解,但是竟然没有写对 T^T

Solution

仍然是DP。

令 $t[i]>t[j]$ ,由题意可列出如下关系式:

将上式展开并化简,得

这样, $j$ 是否能够扩展到 $i$ 只与这两个条件有关。这样可以用其中一个为关键字排序,另一个利用树状数组优化DP即可。

Code

#include <bits/stdc++.h>
using namespace std;
#define N 100005

int w,n,ans,fenwick[N];

struct pie
{
    int x,y,z;
    bool operator <(const pie &a) const
    {
        return x==a.x?y<a.y:x<a.x;
    }
}a[N];

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

void modify(int x,int y)
{
    for(int i=x;i<=n;i+=i&-i)
        fenwick[i]=max(fenwick[i],y);
}

int query(int x)
{
    int re=0;
    for(int i=x;i;i-=i&-i)
        re=max(re,fenwick[i]);
    return re;
}

int main()
{
    cin>>w>>n;
    for(int x,y,i=1;i<=n;i++)
        x=read(), y=read(),
        a[i].x=y+x*2, a[i].y=y-x*2, a[i].z=read();
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) a[i].x=n-i+1, swap(a[i].x,a[i].y);
    sort(a+1,a+n+1);
    for(int temp,i=1;i<=n;i++)
        ans=max(ans,temp=query(a[i].y)+a[i].z),
        modify(a[i].y,temp);
    cout<<ans<<endl;
}