解题思路:双向最长上升/下降子序列
注意事项:
参考代码:
#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 人评分
Hello, world! (C语言代码)浏览:1196 |
【亲和数】 (C语言代码)浏览:538 |
淘淘的名单 (C语言代码)答案错误???浏览:593 |
wu-淘淘的名单 (C++代码)浏览:1331 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:798 |
C语言程序设计教程(第三版)课后习题5.6 (C语言代码)浏览:901 |
IP判断 (C语言代码)浏览:533 |
简单的事情 (C语言代码)浏览:633 |
简单的a+b (C语言代码)浏览:635 |
小O的乘积 (C++代码)浏览:518 |