Removing Cards
National Olympiad — National round (2014 season)
Submission name: game.cpp
Problem summary
Remove all interior cards, one at a time. Removing value v between current neighbors x,y earns v(x+y). Maximize total score; the two endpoint cards remain.
Input
n followed by n card values.
Output
Maximum total score.
Constraints
3 ≤ n ≤ 700; 1 ≤ card value < 1000.
Worked example
An independently prepared example for this explanation.
Input
4 4 5 6 2
Output
86
Solution analysis
- Let dp[l][r] be the best score from removing all cards strictly between endpoints l and r. Adjacent endpoints need no removals, so their value is zero.
- Choose the last removed card k in this interval. Before its removal, the left and right interior intervals have been cleared independently. Its remaining neighbors are exactly l and r, yielding dp[l][k]+dp[k][r]+a[k](a[l]+a[r]). Maximize this over k.
- For 4,5,6,2, remove 5 first for 5(4+6)=50, then 6 for 6(4+2)=36, totaling 86. The opposite removal order yields only 72. Increasing interval width ensures every smaller state is already known.
Why it works
In any removal sequence there is a last interior card k. All earlier removals lie in one of the two subintervals and cannot exceed their optimal scores. The recurrence therefore bounds every sequence above. Conversely, execute optimal sequences for both subintervals and remove k last, attaining each candidate. Induction proves optimality.
Watch out. The score uses the neighbors present at removal time. Do not greedily remove the largest current contribution.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int n;
cin>>n;
vector<long long>a(n);
for(long long&value:a){
cin>>value;
}
vector<vector<long long>>dp(n,vector<long long>(n,0));
for(int width=2;width<n;++width){
for(int left=0;left+width<n;++left){
int right=left+width;
for(int last=left+1;last<right;++last){
// last survives until only the two fixed endpoints remain.
dp[left][right]=
max(dp[left][right],dp[left][last]+dp[last][right]+a[last]*(a[left]+a[right]));
}
}
}
cout<<dp[0][n-1]<<'\n';
}