SRM351 div2 hard
答えみてしもうた。以下は解答の適当日本語訳。
1:選んでやつは消去できると考えられる
2:消去した残りがソートされてればよい
3:選ぶものの合計を最小化したい
4:残されるものの最大化
5:よって、最長増加部分列
#include <algorithm> #include <vector> using namespace std; class InsertSort { public: int calcMinimalCost(vector<int> theArray) { int DP[50]; int n=theArray.size(); int a=0; for(int i=0;i<n;i++) { DP[i]=theArray[i]; for(int j=0;j<i;j++) if(theArray[j]<=theArray[i]) DP[i]=max(DP[i],DP[j]+theArray[i]); a=max(a,DP[i]); } int ans=0; for(int i=0;i<n;i++) ans+=theArray[i]; ans-=a; return ans; } };