ABC163 E - Active Infants

ABC163 E - Active Infants

Question

将一个数组重新排序，每个元素的收益为 $a\left[i\right]\times le{n}_{move}$a[i]×lenmove​，求排序后的最大收益。

Solution

DP
容易想到一个大的值无非放到左边和右边，哪边增加的多放到哪边，但是可能存在放到两边值一样的情况，那么这个时候的选择会影响到之后的选择，所以贪心是不对滴，这里要用到DP。
先排个序，从大到小，然后每次先选未选过的最大的，枚举其在左右的两种情况。
$dp\left[L\right]\left[R\right]=max\left(dp\right[L+1\left]\right[R]+a_{now}\times \mid po{s}_{now}-L\mid ,dp[L\left]\right[R-1]+a_{now}\times \mid po{s}_{now}-R\mid )$dp[L][R]=max(dp[L+1][R]+anow​×∣posnow​−L∣,dp[L][R−1]+anow​×∣posnow​−R∣)
这里看到有两种写法，一种是记忆化搜索，一种是DP，其实感觉记忆化搜索和DP实际上一回事，思想都是不重复找已经找到的量。

Code

记忆化搜索

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 2e3 + 5;

ll n,dp[N][N];
vector<pair<ll,int> >V(n);

ll DP(int L,int R){
	if(R<L) return 0;
	if(dp[L][R]!=-1) return dp[L][R];
	int i=L+n-1-R;
	return dp[L][R]=max(V[i].first*abs(V[i].second-L)+DP(L+1,R),V[i].first*abs(V[i].second-R)+DP(L,R-1));
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=0;i<n;i++){int x;cin>>x; V.push_back({x,i});}
	sort(V.rbegin(),V.rend());
	memset(dp,-1,sizeof(dp));
	cout<<DP(0,n-1);
	return 0;
}

DP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 2000 + 5;

int n;
pair<ll,int> a[N];
ll f[N][N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i].first;
		a[i].second=i;
	}
	sort(a,a+n,greater<pair<int,int> >());
	for(int i=0;i<n;i++){
		for(int j=0;j<=i;j++){
			int k=i-j;
			f[j+1][k]=max(f[j+1][k],f[j][k]+a[i].first*abs(a[i].second-j));
			f[j][k+1]=max(f[j][k+1],f[j][k]+a[i].first*abs(n-k-1-a[i].second));
		}
	}
	ll ans=0;
	for(int i=0;i<=n;i++) ans=max(ans,f[i][n-i]);
	cout<<ans;
	return 0;
}