POJ - 1836 Alignment解题报告（dp求至少删除多少个数可以变成递增数列）

给你一串数，然后问你至少删除多少数，才能让每个满足：至少有一边的所有数都比这个数小。这一串数最多有1000个。

分析：

首先，这一堆数里面肯定有一个最大的数，那么，这个最大的数的左面都是递增的，右面都是递减的。然后就是让谁当最大的是这个。

dp建立：
设l[ i ]表示在选定第 i 个数的前提下，第 i 个数左边至少要删除 l[ i ]个数，才能让该数左边从小到大排列。r[ i ]表示在选定第 i 个数的前提下，第 i个数右边至少要删除 r[ i ]个数，才能让该数右边从大到小排列。
递推关系：l[ i+1 ]=min{ l[ j ]+i-j ( 0<j<=i && a[ j ] > a[ i+1 ] ) };  r[ i ]递推关系同理。
时间复杂度：1000*1000。 
有一个需要注意的地方就是，最高的可能不止一个。解决办法就是，另外创建数组rr[],ll[]。表示的是，以第 i 个数字为最大数，同时可以出现多个最大数的情况下，至少要删除的数的个数。这样每一个 rr[ i ] 和r[ i ]都由 r[ 1]-r[ i-1] 确定。 

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#define N 1050

using namespace std;

double a[N]={0};
int n;
int r[N]={0};
int l[N]={0};
int rr[N]={0};
int ll[N]={0}; 
void ceshi()
{
	for(int i=1;i<=n;i++)
	{
		cout<<l[i]<<" ";
	}
	cout<<endl;
	for(int i=1;i<=n;i++)
	{
		cout<<r[i]<<" ";
	}
	cout<<endl;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	r[n]=l[1]=0;
	rr[n]=ll[1]=0;
	for(int i=2;i<=n;i++)//对于l数组
	{
		l[i]=i-1;
		ll[i]=i-1;
		for(int j=i-1;j>0;j--)
		{
			if(a[j]==a[i])
			{
				if(ll[i]>l[j]+i-1-j)
				{
					ll[i]=l[j]+i-1-j;
				}
				continue;
			}
			if(a[j]>a[i])continue;
			if(l[i]>l[j]+i-1-j)
			{
				l[i]=l[j]+i-1-j;
			}
			if(ll[i]>l[j]+i-1-j)
			{
				ll[i]=l[j]+i-1-j;
			}
		}
	}
	for(int i=n-1;i>0;i--)//对于r数组 
	{
		r[i]=n-i;
		rr[i]=n-i;
		for(int j=i+1;j<=n;j++)
		{
			if(a[j]==a[i])
			{
				if(rr[i]>r[j]+j-i-1)
				{
					rr[i]=r[j]+j-i-1;
				}
				continue;
			}
			if(a[j]>a[i])continue;
			if(r[i]>r[j]+j-i-1)
			{
				r[i]=r[j]+j-i-1;
			}
			if(rr[i]>r[j]+j-i-1)
			{
				rr[i]=r[j]+j-i-1;
			}
		}
	}
	int best=rr[1]+ll[1];
	for(int i=2;i<=n;i++)
	{
		if(best>rr[i]+ll[i])
		{
			best=rr[i]+ll[i];
		}
	}
	//ceshi();
	cout<<best;
}