社区讨论

求助dalao,为什么导弹拦截可以过这题过不了?

P1091[NOIP 2004 提高组] 合唱队形参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mi6urj7y
此快照首次捕获于
2025/11/20 11:09
4 个月前
此快照最后确认于
2025/11/20 11:09
4 个月前
查看原帖
CPP
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define INF -0x3f3f3f3f
int a[50600];
int u[50600];//up
int d[50600];//down
int ans1=INF,n;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)u[i]=d[i]=1;
	
	for(int i=n;i;i--)//down
    for(int j=n;j>i;j--)
        if(a[j]<=a[i])d[i]=max(d[i],d[j]+1);
	 
	for(int i=1;i<=n;i++)//up
	for(int j=1;j<i;j++)
	if(a[j]<a[i])u[i]=max(u[i],u[j]+1);
	
	for(int i=1;i<=n;i++)ans1=max(ans1,(d[i]+u[i])-1);
	cout<<n-ans1;
	return 0;
}
//合唱队形
CPP
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define INF -0x3f3f3f3f
int a[50600];
int u[50600];//up
int d[50600];//down
int ans1=INF,n;
int main()
{
	while(scanf("%d",&a[++n])!=EOF);n--;
	for(int i=1;i<=n;i++)u[i]=d[i]=1;
	
	for(int i=n;i;i--)//down
    for(int j=n;j>i;j--)
        if(a[j]<=a[i])d[i]=max(d[i],d[j]+1);
	for(int i=1;i<=n;i++)ans1=max(ans1,d[i]);
	
	 cout<<ans1<<endl;
	 ans1=INF;
	 
	for(int i=1;i<=n;i++)//up
	for(int j=1;j<i;j++)
	if(a[j]<a[i])u[i]=max(u[i],u[j]+1);
	for(int i=1;i<=n;i++)ans1=max(ans1,u[i]);
	cout<<ans1;
	return 0;
}
//导弹拦截

回复

1 条回复,欢迎继续交流。

正在加载回复...