題意：N位士兵站成一排，長官要請其中的(N-K)位出列，使得剩下的K位士兵排成一等隊形。一等隊形是指這樣的一種隊形：設K位士兵從左到右依次編號為1，2…，K，他們的身高分別為T1，T2，…，TK， 則他們的身高滿足T1<...<Ti，Ti>Ti+1>…>TK(1<=i<=K)。 你的任務是，已知所有N位士兵的身高，計算最少需要幾位士兵出列，可以使得剩下的排成一等隊形。

思路：枚舉一下分割點，然后分別以遞減和遞增討論一下

#include<stdio.h> #include<string.h> #include<queue> #include<cmath> #define MAX 100+10 #define INF 0x3f3f3f3f int n; int dp[MAX]; int a[MAX]; int b[MAX];using namespace std; int up(int l, int r, int tmp) {memcpy(a, b, sizeof(b));for (int i = l; i <= r; i++)dp[i] = 0;a[l - 1] = 0;dp[l - 1] = 0;for (int i = l; i <= r; i++) {for (int j = l - 1; j < i; j++) {if (a[i] >= tmp || a[j] >= tmp)continue;if (a[i] > a[j]) {dp[i] = max(dp[i], dp[j] + 1);}}}int ans = 0;for (int i = l; i <= r; i++) {ans = max(ans, dp[i]);}return r - l + 1 - ans;}int down(int l, int r, int tmp) {memcpy(a, b, sizeof(b));for (int i = l; i <= r; i++)dp[i] = 0;a[l - 1] = INF;dp[l - 1] = 0;for (int i = l; i <= r; i++) {for (int j = l - 1; j < i; j++) {if (a[i] >= tmp)continue;if (a[i] < a[j]) {dp[i] = max(dp[i], dp[j] + 1);}}}int ans = 0;for (int i = l; i <= r; i++) {ans = max(ans, dp[i]);}return r - l + 1 - ans;} int main(void) {while (~scanf("%d", &n)) {for (int i = 1; i <= n; i++)dp[i] = 1;for (int i = 1; i <= n; i++)scanf("%d", &b[i]);int ans = 0;int minn = INF;for (int k = 1; k <= n; k++) {if (k == 1)ans = down(1, n, INF);else if (k == n)ans = up(1, n, INF);else {ans = up(1, k - 1, b[k]) + down(k + 1, n, b[k]);}minn = min(minn, ans);}printf("%d\n", minn);}return 0; }

轉載于:https://www.cnblogs.com/tennant/p/8975781.html

總結

以上是生活随笔為你收集整理的HRBUST 2011【简单dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。