两次DP求最长递增子序列,然后,结果是
// runtime: 3ms // space: 496K #include <iostream> #include <algorithm> using namespace std; const int MAX = 100; int arr1[MAX]; int arr2[MAX]; // reversal of arr1 int dp1[MAX]; // arr1 max increase subsequence int dp2[MAX]; // arr2 max increase subsequence void MaxIncSequence(int* arr, int* dp, int n) { for (int i = 0; i < n; ++i) { dp[i] = 1; for (int j = 0; j < i; ++j) { if (arr[i] > arr[j]) dp[i] = max(dp[i], dp[j] + 1); } } } void Print(int n) { int answer = n; for (int i = 0; i < n; ++i) { answer = min(answer, n - dp1[i] - dp2[n - 1 -i] + 1); } printf("%d\n", answer); } int main() { int n; while (cin>> n) { for (int i = 0; i < n; ++i) { cin>> arr1[i]; arr2[n - 1 - i] = arr1[i]; } MaxIncSequence(arr1, dp1, n); MaxIncSequence(arr2, dp2, n); Print(n); } return 0; }