題目描述： N位同學站成一排，音樂老師要請其中的(N-K)位同學出列，使得剩下的K位同學不交換位置就能排成合唱隊形。 合唱隊形是指這樣的一種隊形：設K位同學從左到右依次編號為1, 2, …, K，他們的身高分別為T1, T2, …, TK， 則他們的身高滿足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)。 你的任務是，已知所有N位同學的身高，計算最少需要幾位同學出列，可以使得剩下的同學排成合唱隊形。 輸入： 輸入的第一行是一個整數N（2 <= N <= 100），表示同學的總數。 第一行有n個整數，用空格分隔，第i個整數Ti（130 <= Ti <= 230）是第i位同學的身高（厘米）。 輸出： 可能包括多組測試數據，對于每組數據， 輸出包括一行，這一行只包含一個整數，就是最少需要幾位同學出列。 樣例輸入： 8 186 186 150 200 160 130 197 220 樣例輸出： 4 來源： 2008年北京大學方正實驗室計算機研究生機試真題
動態規劃求出以每個人結尾的左邊(dp_left[i])和右邊(dp_right[i])的最大隊列長度 枚舉每個人為“中心點”，計算出滿足題目要求的隊列長度（dp[i]），記錄最大值為ans
#include <stdio.h>#define max(x,y) x>y?x:yusing namespace std;int dp_left[101]; //從左到第i個點的最長遞增子序列int dp_right[101]; //從右到第i個點的最長遞增子序列int dp[101]; //為第i個點到左和到右的序列＝dp_right[i]+dp_left[i]-1int list[101];int main() { int n; while (scanf("%d", &n)!=EOF){ for (int i=1; i<=n; i++) { scanf("%d", &list[i]); dp_left[i] = 1; //初始化dp_right和dp_left為1； dp_right[i] = 1; } for (int i=1; i<=n; i++) { //從左到右計算dp_left[i] for (int j=1; j<i; j++) { if (list[j]<list[i]) { dp_left[i] = max(dp_left[i], dp_left[j]+1); } } } for (int i=n; i>=1; i--) { //從右到左計算dp_right[i] for (int j=n; j>i; j--) { if (list[j]<list[i]) { dp_right[i] = max(dp_right[i], dp_right[j]+1); } } } int ans = 1; for (int i=1; i<=n; i++) { //計算dp[i],并紀錄最大值為ans dp[i] = dp_right[i]+dp_left[i]-1; if(dp[i]>ans) ans = dp[i]; }新聞熱點
疑難解答
