P7302 [NOI1998] 免费的馅饼

xiezheyuan · 2022-03-05 14:42:44 · 题解

思路

免费的馅饼，免费的陷阱。

1.贪心做法

先对原数据排序（优先时间从小到大，然后是价值从大到小）。然后跑贪心。先选第一个，然后如果时间足够移动就移动。

时间复杂度是 O(n\log n)。

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

struct Pie{
    int t,p,v;  
} a[100005],last;
int w,n,ans;

bool cmp(Pie x,Pie y){
    if(x.t==y.t){
        return x.v>y.v;
    }
    else{
        return x.t<y.t;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>w>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].t>>a[i].p>>a[i].v;
    }
    sort(a+1,a+n+1,cmp);
    last=a[1];
    ans=a[1].v;
    for(int i=2;i<=n;i++){
        if(2*(a[i].t-last.t)>=abs(a[i].p-last.p)){
            ans+=a[i].v;
            last=a[i];
        }
    }
    cout<<ans<<endl;
    return 0;
}

可以水 50 分。

为什么不是满分，因为本题贪心没有最优解。

2.暴力DP

不难推出，如果设 f[i] 为接住 第 i 个节点，那么枚举 j \in [1,i)。

方程为:

当然，如果要接得到，需要满足 ：

最后的答案就是 ：

当然，边界条件为

时间复杂度是 O(n^2)。

代码如下：

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

int f[100005];
int w,n,ans;

struct pie{
    int t,p,v;
    bool operator<(const pie nth) const {
        return t<nth.t;
    }
} pies[100005];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>w>>n;
    for(int i=1;i<=n;i++){
        cin>>pies[i].t>>pies[i].p>>pies[i].v;
    }
    sort(pies+1,pies+n+1);
    f[1]=pies[1].v;
    for(int i=1;i<=n;i++){
        f[i]=pies[i].v;
        for(int j=1;j<i;j++){
            if(2*(pies[i].t-pies[j].t)>=abs(pies[i].p-pies[j].p)){
                f[i]=max(f[i],f[j]+pies[i].v);
            }
        }
    }
    for(int i=1;i<=n;i++){
        ans=max(f[i],ans);
    }
    cout<<ans<<endl;
    return 0;
}

可以水 85 分。

（开O2 就 90 分了）。

3.树状数组优化DP（正解）

可以考虑对DP方程的条件进行整理，可以得出: