合唱队形(c++),大家帮我看看是哪错了!
问题描述:
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a,b[3000],c[3000],d[3000],maxn,ans=0;
cin>>a;
for(int i=1;i<=a;i++)
{
cin>>b[i];
}
c[1]=1;
for(int i=2;i<=a;i++)
{
maxn=0;
for(int j=1;j<i;j++)
{
if(b[i]>b[j])
{
if(c[j]>maxn)
{
maxn=c[j];
}
}
}
c[i]=maxn+1;
}
d[1]=1;
for(int i=a-1;i>=1;i--)
{
maxn=0;
for(int j=i+1;j<=a;j++)
{
if(b[i]>b[j])
{
if(d[j]>maxn)
{
maxn=d[j];
}
}
}
d[i]=maxn+1;
}
for(int i=1;i<=a;i++)
{
if(c[i]+d[i]>ans)
{
ans=c[i]+d[i];
}
}
cout<<a-(ans-1);
}
答
#include <bits/stdc++.h>
using namespace std;
int a[102], dp1[102], dp2[102];
int n, mid, ans = 0, mx;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
mx = 0;
for (int k = 1; k < j; k++) {
if (a[k] < a[j]) {
mx = max(mx, dp1[k]);
}
}
dp1[j] = mx + 1;
}
for (int j = n; j >= i; j--) {
mx = 0;
for (int k = n; k > j; k--) {
if (a[k] < a[j]) {
mx = max(dp2[k], mx);
}
}
dp2[j] = mx + 1;
}
ans = max(ans, dp1[i] + dp2[i] - 1);
}
printf("%d", n - ans);
return 0;
}