已AC,但有个小问题不是很明白
查看原帖
已AC,但有个小问题不是很明白
1164560
DTNPO楼主2024/7/30 11:21

有疑惑的地方在第47行

为什么最后答案需要多加上一个1呢

#include<iostream>
#include<algorithm>
#include<deque>
#include<string>

using namespace std;

int n;
deque <int> s;
int dp_up[107];
int dp_down[107];

int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	cin >> n; s.push_back(0);
	for(int i=1;i<=n;i++){
		int tem = 0; cin >> tem ;
		s.push_back(tem);
	}
	//input
	
	for(int i=1;i<=n;i++){
		dp_up[i] = 1;
		for(int j=1;j<i;j++){
			if(s[j] < s[i]){
				dp_up[i] = max(dp_up[i], dp_up[j]+1);
			}
		}
	}
	
	for(int i=n;i>=1;i--){
		dp_down[i] = 1;
		for(int j=n;j>i;j--){
			if(s[j] < s[i]){
				dp_down[i] = max(dp_down[i], dp_down[j]+1);
			}
		}
	}
	//********************//
	int ans=0x3f3f3f3f;
	for(int i=1;i<=n;i++){
		ans = min(ans, n-dp_down[i]-dp_up[i]+1);
	}
	//此处为什么刚好需要加上1呢?是因为重复减去了同一个人吗
	//********************//
	cout << ans << endl ;
	
	return 0;
}
/*
8
186 186 150 200 160 130 197 220

4
*/
2024/7/30 11:21
加载中...