學習要點
- 求最長遞增字列
- 求最長遞減子列
題目鏈接
合唱隊_牛客題霸_牛客網
題目描述
解法：動歸求最長遞增子列
#include <iostream>
#include <vector>
using namespace std;int main() {int n;while (cin >> n) {// 輸入的數組int tmp;vector<int> v;for (int i = 0; i < n; ++i) {cin >> tmp;v.push_back(tmp);}// 最長遞增子序列 從左往右if (v.empty()) return 0;vector<int> dp1(n, 1);for (int i = 0; i < n; ++i) {for (int j = 0; j < i ; ++j) {if (v[i] > v[j]) {dp1[i] = max(dp1[i], dp1[j] + 1);}}}// 最長遞減子序列 從右往左if (v.empty()) return 0;vector<int> dp2(n, 1);for(int i = n-1;i>=0;i--){for(int j = n-1;j>i;j--){if(v[i] > v[j]){dp2[i] = max(dp2[i],dp2[j]+1);}}}int result;for(int i =0;i<n;i++){result = max(result,dp1[i]+dp2[i]-1);}cout << n - result;}
}
// 64 位輸出請用 printf("%lld")
)
)
