ZJYYC2360. 圆球的最大得分

思路：这是一道区间dp的题目。最大的数放在最远处会更优，所以每个小孩可以放在 l 处或 r 处，即这段区间的最左边或最右边。这题可以用记忆化搜索来写，用dp[l][r]来记录 i ~ j 之间调整位置后的最大得分。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
#define pii pair<int,int>
const int N=2e3+5;
int dp[N][N];
pii v[N];
int dfs(int i,int l,int r){
    if(r<l) return 0;
    if(dp[l][r]!=-1) return dp[l][r];
    return dp[l][r]=max(v[i].first*abs(v[i].second-l)+dfs(i+1,l+1,r),v[i].first*abs(v[i].second-r)+dfs(i+1,l,r-1));
    // i 是排完序后的第 i 个值，max前一半是 第 i 大的值放在这段区间最左边，后一半是放在这段区间最右边。 
}
signed main(){
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        int x;
        cin >> x;
        v[i]={x,i};
    }
    sort(v+1,v+n+1,greater<pii>());//从大到小排 
    memset(dp,-1,sizeof dp);//初始化 
    cout << dfs(1,1,n) << endl;
    return 0;
}

注：本题出自于AtCoder Beginner Contest 163 E - Active Infants改编。

原文地址：https://blog.csdn.net/2301_81488029/article/details/142734055

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！