Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

dp水过

Posted by 814264306 at 2019-04-19 15:28:16 on Problem 1905
#include<iostream>
using namespace std;
//3 4 5 2 1 5 4 3
void maxList(double a[],int n,int lis[])
{
	int *dp = new int[n+1];
	dp[1] = 1;
	for (int i = 2; i <= n; i++)
	{
		dp[i] = 1;
		for (int j = 1; j < i; j++)
		{
			if (dp[j] + 1 > dp[i] && a[i] > a[j])
			{ 
				dp[i] = dp[j] + 1;
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		if (ans < dp[i])ans = dp[i];
		lis[i] = ans;
	}
}

void minList(double a[], int n,int size,int lms[])
{
	double *b=new double[size-n+1];
	for (int i = n + 1; i <= size; i++)
	{
		b[i - n] = a[size - i+n+1];
	}
	maxList(b, size - n,lms);

}

int main()
{
	double a[1010];
	int n,ans=0,lis[1010],lms[1010];
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}

	maxList(a, n, lis);
	minList(a, 0, n,  lms);
	lis[0] = 0;
	lms[0] = 0;
	for (int i = 0; i <= n; i++)
	{
		int g = lis[i] + lms[n-i];
		//cout << lis[i] << "   ";
		//cout << lms[n-i] << endl;
		if (ans < g)ans = g;
	}
	cout << n - ans << endl;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator