网站建设 长春,c 网站开发入门视频教程,网络服务协议合同,曲阳路街道网站建设题目描述
小x和室友总共 nnn 人#xff0c;组团去打一款游戏#xff0c;总共有 nnn 台电脑供他们使用#xff0c;一人一台#xff0c;最开始#xff0c;第 iii 个人使用第 iii 台电脑。 小x评估了每个人的能力值和临场发挥值。 第 iii 个人的能力值为 aia_iai。 而他们…
题目描述
小x和室友总共 nnn 人组团去打一款游戏总共有 nnn 台电脑供他们使用一人一台最开始第 iii 个人使用第 iii 台电脑。 小x评估了每个人的能力值和临场发挥值。 第 iii 个人的能力值为 aia_iai。 而他们的临场发挥值由能力值和他们所使用的电脑决定。 小x和他的室友喜欢换来换去。 他们惊奇的发现如果第 iii 个人从第 xxx 台电脑换到了第 yyy 台电脑那么第 iii 个人的临场发挥值会增加 ∣x−y∣∗ai|x-y|*a_i∣x−y∣∗ai。 现在他们可以重新任意分配一次电脑。 小x想知道他们的临场发挥值最多会增加多少
输入描述:
第一行一个整数 nnn (2≤n≤2000)(2 \leq n \leq 2000)(2≤n≤2000)。第二行 nnn 个整数 a1,a2,……,ana_1,a_2,……,a_na1,a2,……,an (1≤ai≤109)(1 \leq a_i \leq 10^9)(1≤ai≤109)。
输出描述:
一个整数表示 临场发挥值 最大增加的数量
示例1
输入
复制4 1 3 4 2
4
1 3 4 2
输出
复制20
20
说明
假设第 iii 个人的位置为 cic_ici从 [1,2,3,4][1,2,3,4][1,2,3,4] 更换为 [3,4,1,2][3,4,1,2][3,4,1,2]临场发挥值增加 1×∣1−3∣3×∣2−4∣4×∣3−1∣2×∣4−2∣201 \times |1-3|3 \times |2-4|4 \times |3-1|2 \times |4-2|201×∣1−3∣3×∣2−4∣4×∣3−1∣2×∣4−2∣20
示例2
输入
复制6 8 6 9 1 2 1
6
8 6 9 1 2 1
输出
复制85
85
做法
首先要看出来一个贪心的小结论。就是就是能力值大的应该放在两边反之放中间。
#includebits/stdc.h
#define int long long
using namespace std;int n;
pairint,int a[2010];
int dp[2010][2010];signed main(){scanf(%lld,n);for(int i1;in;i) {int b;scanf(%lld,b);a[i]{b,i};}sort(a1,a1n);for(int i1;in;i){//枚举区间长度和每次取出的数int ba[i].first,ida[i].second;for(int l1;ln-i1;l){//枚举每个长度i的区间求最大值int rli-1;dp[l][r]max(dp[l][r-1]abs(id-r)*b,dp[l1][r]abs(id-l)*b);//b放右边和左边}}coutdp[1][n];}
