NC16664 合唱队形
从左往右求最长上升子序列,在从右往左求最长上升子序列。
#include <iostream> #include <vector> #include <algorithm> using namespace std; const int maxn = 105; int arr[maxn]; vector<int>nums(maxn); int dp[maxn]; int dp2[maxn]; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> arr[i]; nums[i] = arr[i]; } for (int i = 1; i <= n; i++) { dp[i] = 1; for (int j = 1; j < i; j++) { if (arr[j] < arr[i]) { dp[i] = max(dp[j] + 1, dp[i]); } } } reverse(nums.begin() + 1, nums.begin() + 1 + n); for (int i = 1; i <= n; i++) { dp2[i] = 1; for (int j = 1; j < i; j++) { if (nums[j] < nums[i]) { dp2[i] = max(dp2[j] + 1, dp2[i]); } } } int ans = 0; for (int i = 1; i <= n; i++) { ans=max(dp[i]+dp2[n-i+1]-1,ans); } cout << n-ans; /*错误的for循环,请思考一下这两个for循环有什么不同 int ans = 0x3f; for (int i = 1; i <= n; i++) { int temp = dp[i] + dp2[n - i]; ans = min(ans, n - temp); } cout << ans; */ }
题解汇总 文章被收录于专栏
无