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改编。