BZOJ 2131 免费的馅饼

题目链接https://www.lydsy.com/JudgeOnline/problem.php?id=2131

题意:有n个从天而降的馅饼,会告诉你每个馅饼掉落的地点时间以及馅饼的价值,刚开始你可以站在任意一个位置,之后你每秒可以向左或向右移动1个或2个单位,也可以不动,问能获得的最大价值。

思路:我们考虑两个馅饼i,j,它们都可以用一个三元组表示(t_i,pos_i,val_i),(t_j,pos_j,val_j),假设t_j>t_i根据题意我们可以列出这么一个表达式|pos_i-pos_j|\le 2t_j-2t_i我们拆掉绝对值然后移一下项可以得到以下式子\begin{matrix}2t_i+pos_i\le 2t_j+pos_j\\2t_i-pos_i\le 2t_j-pos_j\end{matrix}.所以我们做一下坐标变换,发现这就是经典的带权LIS问题,树状数组优化DP即可,时间复杂度O(nlogn)

#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=1e5+10;
struct Node{
    int x,y,v;
    bool operator<(const Node&rhs)const{
        if (x==rhs.x) return y>rhs.y;
        return x<rhs.x;
    }
}coin[N];
int w,n,m,i,p,t,v,ans,dp[N],mx[N];
vector<int>vec;
void compress(){
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end());
    for (i=1;i<=n;++i){
        int pos=lower_bound(vec.begin(),vec.end(),coin[i].y)-vec.begin();
        coin[i].y=pos+1;
    }
    m=(int)vec.size();
}
inline int lowbit(int x){return x&(-x);}
void update(int x,int p){for (;x<=m;x+=lowbit(x)) mx[x]=max(mx[x],p);}
int query(int x){
    int ret=0;
    for (;x>0;x-=lowbit(x)) ret=max(ret,mx[x]);
    return ret;
}
int main(){
    read(w),read(n);
    for (i=1;i<=n;++i){
        read(t),read(p),read(v);
        coin[i].x=2*t+p;
        coin[i].y=2*t-p;
        coin[i].v=v;
        vec.PB(coin[i].y);
    }
    compress();
    sort(coin+1,coin+1+n);
    for (i=1;i<=n;++i){
        dp[i]=query(coin[i].y)+coin[i].v;
        ans=max(ans,dp[i]);
        update(coin[i].y,dp[i]);
    }
    printf("%d\n",ans);
    return 0;
}

发表评论

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