tjjjj

allqpsi · 2024-01-20 07:33:34 · 题解

思路：

第一眼看到这道题，认为是一个贪心。随便从大到小排序了一下数组，每次看移到最左边更远还是最右边更远，然后移到那。不多说，明显 WA 了。

仔细一想，居然贪心是错的，那正解应该就是 dp 了。再一想，这题就是区间 dp 嘛！从贪心来思考，我们可以对左右端点分别放几个数 dp 这样思路就来了。可这未免也太麻烦了。

反过来想，我们可以枚举中间一段。将数组从小到大排，依次放入中间。设 f_{i,j} 是指将最小的数依次插入，从 i 到 j 最优解，得转移方程：

f[j][t]=max(f[j][t],max(f[j+1][t]+vi[t-j+1].x*abs(vi[i].id-j),f[j][t-1]+vi[t-j+1].x*abs(vi[i].id-t)));

(本人 LATEX 打的有点烦，用代码形式展示公式，请谅解。)

最后贴上代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
    int x,id;
};
int f[2005][2005],n,t,ans=0;
node vi[2005];
bool cmp(node a,node b){
    return a.x<b.x;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>vi[i].x;
        vi[i].id=i;
    }
    sort(vi+1,vi+1+n,cmp);
    for(int i=1;i<=n;i++){
        for(int j=1;j+i-1<=n;j++){
            t=i+j-1;
            f[j][t]=max(f[j][t],max(f[j+1][t]+vi[t-j+1].x*abs(vi[i].id-j),f[j][t-1]+vi[t-j+1].x*abs(vi[i].id-t)));
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            ans=max(ans,f[i][j]);
        }
    }
    cout<<ans;
}