最少攔截系統

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 53723????Accepted Submission(s): 21061

Problem Description 某國為了防御敵國的導彈襲擊,發展出一種導彈攔截系統.但是這種導彈攔截系統有一個缺陷:雖然它的第一發炮彈能夠到達任意的高度,但是以后每一發炮彈都不能超過前一發的高度.某天,雷達捕捉到敵國的導彈來襲.由于該系統還在試用階段,所以只有一套系統,因此有可能不能攔截所有的導彈.
怎么辦呢?多搞幾套系統唄!你說說倒蠻容易,成本呢?成本是個大問題啊.所以俺就到這里來求救了,請幫助計算一下最少需要多少套攔截系統. Input 輸入若干組數據.每組數據包括:導彈總個數(正整數),導彈依此飛來的高度(雷達給出的高度數據是不大于30000的正整數,用空格分隔) Output 對應每組數據輸出攔截所有導彈最少要配備多少套這種導彈攔截系統. Sample Input 8 389 207 155 300 299 170 158 65 Sample Output 2 因為沒有給導彈個數的范圍，所以不敢開數組去存下來，只好往著邊輸入邊解決的方法去計算。 思路：暴力更新區間。 1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 const int maxn=30006; 5 bool dp[maxn]; 6 7 int main() 8 { 9 int n; 10 while( ~scanf("%d",&n)){ 11 int top=0,ans=0,num; 12 memset( dp, false, sizeof dp); 13 for(int i=1;i<=n;i++){ 14 scanf("%d",&num); 15 if(num>=top){ 16 ans++; 17 dp[num]=true; 18 top=num; 19 } 20 else{ 21 int j; 22 for(j=num;j<=top;j++){ 23 if(dp[j]) break; 24 } 25 if(j==top){ 26 dp[top]=false; 27 dp[num]=true; 28 top=num; 29 } 30 else{ 31 dp[j]=false; 32 dp[num]=true; 33 } 34 } 35 } 36 printf("%d\n",ans); 37 } 38 return 0; 39 }

因為這道題目的是被某神放在dp里面，本菜雞實在是沒有想到dp的方法，就上網查題解看有沒有人用dp去做的。

發現真的可以把導彈的每一個都存下來，然后用LIS。。。

說實話，把每個導彈的高度都存下來我就沒有想。然而，確實能存。

下面的代碼來自：https://blog.csdn.net/hurmishine/article/details/52926957

1 #include<cstdio> 2 const int maxn=10000; 3 int a[maxn],dp[maxn]; 4 int n; 5 6 int LIS() 7 { 8 dp[1]=1; 9 int ans=1; 10 for(int i=2;i<=n;i++){ 11 int m=0; 12 for(int j=1;j<i;j++){ 13 if(dp[j]>m&&a[j]<a[i]) 14 m=dp[j]; 15 } 16 dp[i]=m+1; 17 if(dp[i]>ans) 18 ans=dp[i]; 19 } 20 return ans; 21 } 22 23 int main() 24 { 25 while( ~scanf("%d",&n)){ 26 for(int i=1;i<=n;i++) 27 scanf("%d",&a[i]); 28 printf("%d\n",LIS()); 29 } 30 return 0; 31 }

?

?

轉載于:https://www.cnblogs.com/ZQUACM-875180305/p/9090234.html

總結

以上是生活随笔為你收集整理的hdoj 1257(暴力)的全部內容，希望文章能夠幫你解決所遇到的問題。

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