免费的馅饼 – HYSBZ 2131 – 树状数组+DP

来源: 免费的馅饼 – HYSBZ 2131 – Virtual Judge

对于两个馅饼i,j,他们分别有自己的t,pos,val。

假设tj>ti,根据题意可以得出

去掉绝对值后就是

然后求解,我们将结构体按照优先2*t+p的顺序递增排序,然后按顺序遍历,所以第一个式子一定是成立的。对于第二个式子,我们用树状数组来维护小于等于2*t-p的权值和就好了。

 

 
代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;

struct node
{
    int t,p,v,x,y;
}a[maxn];

int mp[maxn],dp[maxn],f[maxn];

int m;

bool cmp(node a,node b)
{
    if(a.x==b.x)return a.y<b.y;
    else return a.x<b.x;
}

int lowbit(int x)
{
    return x&(-x);
}

int query(int x)
{
    int ans=0;
    while(x)
    {
        ans=max(ans,f[x]);
        x-=lowbit(x);
    }
    return ans;
}

void updata(int x,int v)
{
    while(x<=m)
    {
        f[x]=max(f[x],v);
        x+=lowbit(x);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    int w,n;
    cin>>w>>n;
    for(int i=1;i<=n;i++)
    {
        int t,p,v;
        cin>>t>>p>>v;
        a[i]={t,p,v,2*t+p,2*t-p};
        mp[i]=a[i].y;
    }
    sort(mp+1,mp+1+n);
    m=unique(mp+1,mp+1+n)-mp-1;
    for(int i=1;i<=n;i++)
    {
        a[i].y=lower_bound(mp+1,mp+1+m,a[i].y)-mp;
    }
    sort(a+1,a+1+n,cmp);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        dp[i]=query(a[i].y)+a[i].v;
        ans=max(ans,dp[i]);
        updata(a[i].y,dp[i]);
    }
    cout<<ans<<endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注