ABC163 E - Active Infants

ABC163 E - Active Infants

Question

하나의 그룹을 다시 정렬하고, 각 요소의 수익은 a[i]× l e n m o v e a[i]\times len_{move} a[i]×lenmove, 정렬 후 최대 수익을 구합니다.

Solution

DP는 큰 값을 왼쪽과 오른쪽에 두고, 어느 쪽이 더 늘어나면 어느 쪽에 두는지 생각하기 쉽다. 그러나 양쪽 값과 같은 상황이 존재할 수 있다. 그러면 이때의 선택이 이후의 선택에 영향을 줄 수 있기 때문에 욕심을 부리는 것은 옳지 않다. 여기에 DP를 사용해야 한다.먼저 큰 것부터 작은 것까지 순서를 정한 다음에 매번 선택하지 않은 가장 큰 것을 골라 좌우에 있는 두 가지 상황을 열거한다.d p [ L ] [ R ] = m a x ( d p [ L + 1 ] [ R ] + a n o w × ∣ p o s n o w − L ∣ , d p [ L ] [ R − 1 ] + a n o w × ∣ p o s n o w − R ∣ ) dp[L][R] = max(dp[L+1][R] + a_{now}\times\left | pos_{now} - L\right |,dp[L][R-1]+a_{now}\times\left | pos_{now} - R\right | ) dp[L][R]=max(dp[L+1][R]+anow​×∣posnow​−L∣,dp[L][R−1]+anow​×Posnow - R R∣) 여기서 보면 두 가지 문법이 있는데 하나는 기억화 검색이고 하나는 DP이다. 사실 기억화 검색과 DP는 실제적인 일이라고 느끼고 사상은 이미 찾은 양을 반복하지 않는다.

Code

기억화 검색

#include
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
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;
}