1 solutions
-
0
每个人身高为a[i],分别记录当i作为队伍中最高的人时左边有几个人,右边几个人。
ac code
#include<bits/stdc++.h> typedef long long LL; using namespace std; int n,a[110],ans; int f[110],g[110]; int main () { 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[j] < a[i])f[i] = max(f[i],f[j] + 1); } } for(int i = n;i >= 1;-- i) { g[i] = 1; for(int j = n;j > i;-- j) { if(a[j] < a[i])g[i] = max(g[i],g[j] + 1); } } for(int i = 1;i <= n;++ i) { ans = max(f[i] + g[i] - 1,ans); } cout << n - ans; return 0; }
- 1
Information
- ID
- 6866
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- 10
- Tags
- (None)
- # Submissions
- 1
- Accepted
- 1
- Uploaded By