连续递增子串.txt

一些典型DP题的代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;

//连续递增子串 动态规划
//本题对应NOJ上的1008 
int a[105];

int cal(int num)
{
	int i,k,max,max2;
	int left[105],ltotle[105];//left[i]表示从左数起，以i为末元素的连续递增子串的最大长度
	int right[105],rtotle[105];//ltotle[i]表示从左数起，一直到i，所包含的连续递增子串的最大长度
	left[1]=1;right[1]=1;
	for(i=2;i<=num;i++)
	{
		max=0;max2=0;
		for(k=1;k<i;k++)
		{
			if(a[k]<a[i])
				if(max<left[k]) max=left[k];
			if(a[num-i+1]>a[num-k+1])
				if(max2<right[k]) max2=right[k];
		}
		left[i]=max+1;//left[i]=max{left[k]}+1 (1<=k<i,a[k]<a[i])
		right[i]=max2+1;
	}
	ltotle[1]=left[1];rtotle[1]=right[1];
	for(i=2;i<=num;i++)
	{
		max=0;max2=0;
		for(k=1;k<=i;k++)
		{
			if(max<left[k]) max=left[k];
			if(max2<right[k]) max2=right[k];
		}
		ltotle[i]=max;rtotle[i]=max2;
	}
	max=0;
	for(i=1;i<=num;i++)
		if(max<ltotle[i]+rtotle[num-i+1]) max=ltotle[i]+rtotle[num-i+1];
	return num-(max-1);
}

int main()
{
	int num,i;
	scanf("%d",&num);
		for(i=1;i<=num;i++)
		cin>>a[i];
	cout<<cal(num)<<endl;
	return 0;
}



/*
int cal(int num)
{
	int i,max=0;
	int left[105],right[105];
	memset(left,0,sizeof(left));
	memset(right,0,sizeof(right));
	for(i=2;i<=num;i++)
	{
		if(a[i-1]<a[i]) left[i-1]++;
		left[i]+=left[i-1];
		if(a[num-i+1]>a[num-i+2]) right[num-i+1]++;
		right[num-i+1]+=right[num-i+2];
	}
	for(i=1;i<=num;i++)
		if(left[i]+right[i]>max) max=left[i]+right[i];
	return num-(max+1);
}
*/

/*
int cal(int num)
{
	int i,k,max,max2;
	int left[105],ltotle[105];
	int right[105],rtotle[105];
	left[1]=1;right[1]=1;
	for(i=2;i<num;i++)
	{
		max=0;max2=0;
		for(k=1;k<i;k++)
		{
			if(a[k]<a[i])
			{
				if(max<left[k]+1) max=left[k]+1;
			}
			else if(max<left[k]) max=left[k];
			if(a[num-i+1]>a[num-k+1])
			{
				if(max2<right[k]+1) max2=right[k]+1;
			}
			else if(max2<right[k]) max2=right[k];
			left[i]=max;
			right[i]=max2;
		}
	}
	ltotle[1]=left[1];rtotle[1]=right[1];
	for(i=2;i<=num;i++)
	{
		max=0;max2=0;
		for(k=1;k<=i;k++)
		{
			if(max<left[k]) max=left[k];
			if(max2<right[k]) max2=right[k];
		}
		ltotle[i]=max;rtotle[i]=max2;
	}
	max=0;
	for(i=1;i<=num;i++)
		if(max<ltotle[i]+rtotle[num-i+1]) max=ltotle[i]+rtotle[num-i+1];
	return num-(max-1);
}
*/