E - Active Infants （贪心&DP）

此题贪心的思路是优先对较大的数往两边放。可以有两种方法：1.递归+类似区间DP形式 2.设dp[ i ][ j ]表示往左放的个数和往右放的个数从小到大递推。具体看代码。

法1：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e3+5;
vector<pair<ll,ll> >v(N);//vector对pair排序时按'键'排序 即第一元素first 
ll dp[N][N];
int n;
ll fun(int l,int r){
	if(l>r) return 0;
	if(dp[l][r]) return dp[l][r];
	int i=n-(r-l+1);//当前要放入的数的下标 
	return dp[l][r]=max(fun(l,r-1)+v[i].first*(r-v[i].second),fun(l+1,r)+v[i].first*(v[i].second-l));//放两端取最大 
}
int main(){
	scanf("%d",&n);
	for(int i=0,x;i<n;i++)
		scanf("%d",&x),v.push_back({x,i});
	sort(v.rbegin(),v.rend());//贪心从大到小排 
	fun(0,n-1);
	printf("%lld\n",dp[0][n-1]);
	return 0;
}

法2：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e3+5;
ll dp[N][N];
struct p{
	int x,id;
	bool operator<(const p&a)const{
		return x>a.x; 
	}
}a[N];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i].x),a[i].id=i;
	sort(a+1,a+n+1);//从大到小排序 
	for(int k=1;k<=n;k++)//对第k个元素进行放置(前k-1个元素所有情况都已知) 
		for(int i=0;i<k;i++)//遍历前k-1元素的所有情况. i为往左放置的个数. 
		{
			int j=k-1-i;//前k-1元素往右放置的个数. 
			dp[i+1][j]=max(dp[i+1][j],dp[i][j]+(ll)a[k].x*(a[k].id-(i+1)));//往左放 
			dp[i][j+1]=max(dp[i][j+1],dp[i][j]+(ll)a[k].x*(n-j-a[k].id));//往右放 
		}
	ll ans=0;
	for(int i=0;i<=n;i++) ans=max(ans,dp[i][n-i]);//取最大值. 
	printf("%lld\n",ans);
	return 0;
}