解题思路:双向最长上升/下降子序列
注意事项:
参考代码:
#include<iostream> #include<algorithm> using namespace std; const int N = 1e2 + 10; int a[N], f[N], g[N]; int main() { int n; cin >> n; for(int i = 1; i <= n; i ++) cin >> a[i]; for(int i = 1; i <= n; i ++) { f[i] = 1; for(int j = 1; j <= i; j ++){ if(a[i] > a[j]) f[i] = max(f[i],f[j] + 1); } } for(int i = n; i >= 1; i --) { g[i] = 1; for(int j = i + 1; j <= n; j ++){ if(a[i] > a[j]) g[i] = max(g[i],g[j] + 1); } } int res = 0; for(int i = 1; i <= n; i ++) res = max(f[i] + g[i], res); cout << n - res + 1; return 0; }
0.0分
1 人评分
C语言训练-最大数问题 (C语言代码)浏览:633 |
C语言训练-求具有abcd=(ab+cd)2性质的四位数 (C语言代码)浏览:562 |
C语言程序设计教程(第三版)课后习题10.4 (C语言代码)浏览:665 |
C语言程序设计教程(第三版)课后习题6.5 (C语言代码)浏览:624 |
蓝桥杯历届试题-翻硬币 (C++代码)浏览:872 |
C语言训练-自守数问题 (C语言代码)浏览:740 |
C语言程序设计教程(第三版)课后习题7.3 (C语言代码)浏览:403 |
C语言训练-8除不尽的数 (C语言代码)浏览:1396 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:376 |
小O的数字 (C++代码)浏览:757 |