合唱队形(c++DP)

 首先，先看一下我得了20分的代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b[101],c[101],d[101],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);
}
           

看出问题了吗？

我没有给所有数组初始化。

所以，很悲惨的WA了

AC代码：

#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[i]=1,d[i]=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;
	}
	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);
}