[SDOI2008] Sue 的小球

链接

嗯,不好写

这题思路与上一个帖子的思路有一点像(也许也不像?)

我们可以先计算总的价值,然后计算收集完所有的彩蛋损失的最小价值,最后一减去除以1000.0就是答案了

我们将所有的彩蛋按x的大小排个序

定义dp[l][r][0]和dp[l][r][1]表示收集完区间[l,r]且在最左端或者最右端的彩蛋损失的最小价值,接着只有两种可能

1:往左走dp[l-1][r][0]

2:忘右走dp[l][r+1][1]

中途损失的价值,就是除去[l,r]的速度乘上所花的时间,用前缀和计算

遍历每一个区间就行

记得开long long

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
int dp[2005][2005][2];

signed main(){
    int n,x0;
    cin>>n>>x0;
    
    for(int i=0;i<2005;i++)
        for(int j=0;j<2005;j++)
            dp[i][j][0]=dp[i][j][1]=INF;
    vector<pair<int,int>>eggs(n+1);
    vector<int>y(n+1,0);
    vector<int>Sum(n+1,0);
    int sum=0;
   
    eggs[0].first=x0,eggs[0].second=0;
    for(int i=1;i<=n;i++){
        cin>>eggs[i].first;
    }
    for(int i=1;i<=n;i++){
        cin>>y[i];
        sum+=y[i];
    }
    for(int i=1;i<=n;i++){
        cin>>eggs[i].second;
    }
    sort(eggs.begin(),eggs.end(),[](pair<int,int>x,pair<int,int>y){
        return x.first<y.first;
    });
    for(int i=0;i<=n;i++){
        if(i==0) Sum[i]=eggs[i].second;
        else Sum[i]=eggs[i].second+Sum[i-1];
    }
    int start=lower_bound(eggs.begin(),eggs.end(),x0,
                          [](pair<int,int>x,int val){
    return x.first<val;
    })-eggs.begin();
    dp[start][start][0]=dp[start][start][1]=0;
    for(int len=1;len<=n;len++){
        for(int l=0;l<=n-len+1;l++){
            int r=l+len-1;
            if(dp[l][r][0]!=INF){
                int s=(l>0?Sum[l-1]:0)+Sum[n]-Sum[r];
                if(l>0) dp[l-1][r][0]=min((eggs[l].first-eggs[l-1].first)*s+dp[l][r][0],dp[l-1][r][0]);
                if(r<n) dp[l][r+1][1]=min((eggs[r+1].first-eggs[l].first)*s+dp[l][r][0],dp[l][r+1][1]);
            }
            if(dp[l][r][1]!=INF){
                int s=(l>0?Sum[l-1]:0)+Sum[n]-Sum[r];
                if(l>0) dp[l-1][r][0]=min((eggs[r].first-eggs[l-1].first)*s+dp[l][r][1],dp[l-1][r][0]);
                if(r<n) dp[l][r+1][1]=min((eggs[r+1].first-eggs[r].first)*s+dp[l][r][1],dp[l][r+1][1]);
            }
        }
    }
    double ans=(double)(sum-min(dp[0][n][0],dp[0][n][1]))/1000.0;
    cout<<fixed<<setprecision(3)<<ans;
}

时间复杂度:O(n²)

空间复杂度:O(n²)