当前位置:网站首页>P1091 chorus formation (DP & LIS)

P1091 chorus formation (DP & LIS)

2021-08-10 08:05:07 wx6110fa547fd20

P1091 Chorus formation (DP&LIS)

  Subject portal

Ideas : Obviously running both sides LIS, Go through it and get the most value . Time complexity :O(n^2) But it can be used upper_bound() Press to O(nlogn) This practice is not written here ....

AC Code :

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int a[N],dp[2][N];// preservation [1,n] and [n,1] Of LIS 
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	dp[0][1]=dp[1][n]=1;
	for(int i=2,mx;i<=n;i++){ // Run both sides LIS 
			mx=0;
		for(int j=1;j<i;j++)
			if(a[j]<a[i]&&dp[0][j]>mx)
				mx=dp[0][j];
		dp[0][i]=mx+1;
	}
	for(int i=n-1,mx;i>=1;i--){
			mx=0;
		for(int j=n;j>i;j--)
			if(a[j]<a[i]&&dp[1][j]>mx)
				mx=dp[1][j];
		dp[1][i]=mx+1;
	}
	int ans=0;
	for(int i=1;i<=n;i++)// Traverse to get the maximum value . 
		ans=max(ans,dp[0][i]+dp[1][i]-1);
	printf("%d\n",n-ans);
	return 0;
}

      
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.

版权声明
本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/08/20210810080205615z.html

随机推荐