首页 > 代码库 > 合唱队
合唱队
#include <iostream>
using namespace std;
int main()
{
int N = 0;
while(cin>>N)
{
int *students = new int [N + 1];//students[0]保留不用
memset(students, 1, sizeof(int) * (N +1));
for (int i =1; i <= N; ++i)
{
cin>>students[i];
}
int *inc1 = new int[N + 1];
int *inc2 = new int[N + 1];
memset(inc1, 0 , sizeof(int)*(N+1));
memset(inc2, 0 , sizeof(int)*(N+1));
inc1[1] = 1;
for (int i = 2; i <= N ; i++)
{
inc1[i] = 1;
for (int j = 1; j < i; j++)
{
if (students[i] > students[j] && inc1[j] + 1 > inc1[i])
{
inc1[i] = inc1[j] + 1;
}
}
}
inc2[N] = 1;
for (int i = N - 1; i >= 1; i--)
{
inc2[i] = 1;
for (int j = N; j > i; j--)
{
if ((students[i] > students[j]) && (inc2[j]+1 > inc2[i]))
{
inc2[i] = inc2[j]+1;
}
}
}
int max = 0;
for (int i = 1; i <= N; i++)
{
if (max < inc1[i] +inc2[i] - 1)
{
max = inc1[i] +inc2[i] -1;
}
}
cout<<N - max<<endl;
delete [] students;
}
return 0;
}
using namespace std;
int main()
{
int N = 0;
while(cin>>N)
{
int *students = new int [N + 1];//students[0]保留不用
memset(students, 1, sizeof(int) * (N +1));
for (int i =1; i <= N; ++i)
{
cin>>students[i];
}
int *inc1 = new int[N + 1];
int *inc2 = new int[N + 1];
memset(inc1, 0 , sizeof(int)*(N+1));
memset(inc2, 0 , sizeof(int)*(N+1));
inc1[1] = 1;
for (int i = 2; i <= N ; i++)
{
inc1[i] = 1;
for (int j = 1; j < i; j++)
{
if (students[i] > students[j] && inc1[j] + 1 > inc1[i])
{
inc1[i] = inc1[j] + 1;
}
}
}
inc2[N] = 1;
for (int i = N - 1; i >= 1; i--)
{
inc2[i] = 1;
for (int j = N; j > i; j--)
{
if ((students[i] > students[j]) && (inc2[j]+1 > inc2[i]))
{
inc2[i] = inc2[j]+1;
}
}
}
int max = 0;
for (int i = 1; i <= N; i++)
{
if (max < inc1[i] +inc2[i] - 1)
{
max = inc1[i] +inc2[i] -1;
}
}
cout<<N - max<<endl;
delete [] students;
}
return 0;
}
合唱队
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。