HDU - 1257 —— 最少拦截系统 —— dp+贪心

8 389 207 155 300 299 170 158 65

2

这道题其实刚开始想的复杂了，因为之前做过一道树状数组的题目。我就想用其中的算法，可以求得每一个导弹后面高度大于自己的导弹的数目。

是想出来以后，每次从前面的话会受后面导弹的影响，但是如果从那个后面处理的话，不能够及时对前面的导弹做出更新。所以我放弃了这种做法.

用dp的思路就是开始没有任何一条系统，直到发现当前系统最小的不能够大于新来的导弹高度时就ans ++;就相当于是增加了一条新的控制系统。

贪心体现在每次选择和当前所有的系统中最接近的系统匹配。

注：注释部分是刚开始的错误思路。。

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <stack>
#include <map>
#include <vector>
#include <cmath>
#include <algorithm>using namespace std;#define MAX_N 100005
#define INF 0x3f3f3f3f
#define Mem(a,x) memset(a,x,sizeof(a))
#define ll long longint h[MAX_N],tree[MAX_N],m[MAX_N],dp[MAX_N];
bool vis[MAX_N];
//int lowbit(int x)
//{
//    return x&(-x);
//}
//void che(int p,int r)
//{
//    for(int i = p; i<=MAX_N; i+=lowbit(i))
//    {
//        tree[i] += r;
//    }
//}
//int sum(int x)
//{
//    int con = 0;
//    for(int i = x; i>=1; i-=lowbit(i))
//    {
//        con += tree[i];
//    }
//    return con;
//}
int main()
{int n;while(~scanf("%d",&n) && n){
//        Mem(vis,false);
//        Mem(tree,0);//dp[0] = INF;int ans = 0,g;for(int i = 0; i<n; i++){scanf("%d",&g);if(ans == 0) dp[ans] = g;int mint = INF,cur;bool flag = false;for(int j = 0; j<ans; j++) {if(g < dp[j] && mint > dp[j]-g) {mint = dp[j] - g;flag = true;cur = j;}}if(flag) {dp[cur] = g;}else {dp[ans] = g;ans ++;}}printf("%d\n",ans);
//        for(int i = n-1; i>=0; i--)
//        {
//            che(h[i],1);
//            int ans = 0;
//            ans = n-i-1-sum(h[i]-1);
//            m[i] = ans; // 记录每个导弹后面比它自己还要高的导弹的个数
//        }cout<<endl;for(int i = 0; i<n; i++) cout<<m[i]<<' ';cout<<endl;
//        int getc = 0,ans = 0;
//        for(int i = 0; i<n; i++)
//        {
//            if(vis[i]) continue;
//            vis[i] = true;
//            int f = 1,cur = 0;
//            for(int j = n-1; j>i; j--)
//            {
//                if(!vis[h[j]] && f)
//                {
//                    vis[h[j]] = true;
//                    f = 0;
//                    cur = m[j];
//                }
//                if(m[j] >= cur && !vis[h[j]]) {
//                    vis[h[j]] = true;
//                    cur = m[j];
//                }
//            }
//            ans ++;
//            if(f) break;
//        }
//        cout<<ans<<endl;//        while(true) {
//            Mem(dp,0);
//            for(int i = 0; i<n; i++) {
//                dp[i] = 1;
//                for(int j = 0; j<i; j++) {
//                    if(h[i] < h[j]) {
//                        dp[i] = max(dp[i],dp[j]+1);
//                    }
//                }
//            }
//        }}return 0;
}