入侵和反擊

時間限制:?1 Sec??內存限制:?128 MB

題目描述

A國部署的反導系統遇到了一個致命BUG，那就是每一次發射的攔截導彈的飛行高度都將只能小于等于上一枚導彈的飛行高度，第一次發射的攔截導彈的飛行高度可以看作是足夠大。對于A國，這是一件很嚴重的問題，這意味著A國的防空系統面臨空前危機。

通過對A國的軍事部門計算機的入侵，A國還不知道敵對國B國剛才已經發現了這項BUG。更不知道，在這項BUG的報告書上交到B國空軍司令部那一刻，三分鐘后B國的全體高級空軍軍官已經在作戰室討論作戰方案。

如果戰爭真的開始，B國將依次派出n架戰斗機A國將依次發射攔截導彈，這n架飛機的飛行高度分別是h1h2h3.....hn。B國將要充分利用這項漏洞，考慮到這么一種情況，假設只要A國的導彈的飛行高度大于等于B國飛機就能百分之百地鎖定并擊落，那么B國，最少將會有幾架不被擊落飛機？

輸入

第一行為T，表示有T組輸入數據(T<200)。

每組數據第一行是n代表有n架飛機（1=<n<=20 000）。

接下來一行有n個數，分別代表n架飛機的飛行高度，飛機飛行高度maxh為(1<=maxh<=50 000)。

輸出

對于每組測試數據，在每行中輸出一個數。表示B國最少將會有幾架未被擊落飛機。

樣例輸入

2 1 1000 6 340 260 101 405 278 89

樣例輸出

0

2

分析：

動態規劃基礎題目，求一個最長上升子序列，總序列長度減去上升子序列長度，即為答案

解法1：時間復雜度：O（n^2）

#include<stdio.h> #define MAXN 20010 int dp[MAXN], a[MAXN]; int main() {int n, i, j, t, temp;int max, min;scanf("%d", &t);while (t--) {scanf("%d", &n);for (i = 1; i <= n; i++)scanf("%d", &a[i]);dp[1] = 1;// max=5000;for (i = 2; i <= n; i++){temp = 0;for (j = 1; j < i; j++)if (a[i] <= a[j])if (temp < dp[j])temp = dp[j];dp[i] = temp + 1;}max = 0;for (i = 1; i <= n; i++)if (max < dp[i])max = dp[i];min = n - max;printf("%d\n", min);}return 0; }

解法2：時間復雜度O（n^2）

//lower_bound返回區間[first, last)內第一個不小于（即大于或等于）給定值的元素指針 //upper_bound返回區間[first, last)內第一個大于給定值的元素指針 #include<stdio.h> #include<algorithm> #include<cstring> using namespace std; int num[20100],lis[20100]; int main() {int n,len,T;scanf("%d",&T);while(T--){scanf("%d",&n);len = 0;memset(lis,0,sizeof(lis));for(int i=n-1;i>=0;i--) //如果i是從1開始，在lower_bound中的到的位置會返回到0， //這樣就不可以把lis[1]的位置替換掉，從而WA。scanf("%d",&num[i]);lis[0] = num[0];for(int i=1;i<n;i++){if(num[i] >= lis[len]) //如果num比lis[len]選擇的終點大，則可以放入lis，即新的終點。lis[++len] = num[i];else{int pos = upper_bound(lis,lis+len,num[i]) - lis; //注意lower_bound 的用法，lower_bound返回的是一個地址lis[pos] = num[i];}}printf("%d\n",n-len-1);//len是從0開始的，所以要加上1。} }

?

總結

以上是生活随笔為你收集整理的入侵和反击 动态规划的全部內容，希望文章能夠幫你解決所遇到的問題。

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