思路
看题目中给出的式子，其实就是一半是最长上升子序列，一半是最长下降子序列。那么就需要进行两次DP，第一次求最长上升子序列，第二次求最长下降子序列，然后枚举序列的最高点。这个从这个最高点劈开。维护一个最大的值。到最后有总人数减去最大值
代码
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int dp[233], n, t[123], ans, f[233], Ans;
int main() {
scanf("%d", &n);
for(int i=1; i<=n; i++) scanf("%d", &t[i]);
t[0] = 0;
for(int i=1; i<=n; i++) {
for(int j=0; j<i; j++) {
if(t[j] < t[i]) dp[i] = max(dp[i], dp[j]+1);
}
}
t[n+1] = 0;
for(int i=n; i>=1; i--) {
for(int j=n+1; j>i; j--) {
if(t[j] < t[i]) f[i] = max(f[i], f[j]+1);
}
}
for(int i=1; i<=n; i++) Ans = max(dp[i] + f[i] - 1, Ans);
printf("%d", n-Ans);
}
转载于:https://www.cnblogs.com/bljfy/p/9335957.html
相关资源：锣鼓声声迎新春——新年工作计划ppt模板.zip
