题解 P1020 【导弹拦截】

· · 题解

深搜+贪心

看到各位dalao各种dp和什么什么序列，身为一名准初一蒟蒻的我深深地自愧不如，在此提供一种比较新的思路（逃）。

第一问我用的是dfs（话说记搜和dp差不多啊......dp党不要喷我），第二问我用的是贪心+模拟，感觉好理解一点。

第一问很简单，对于每一枚导弹，如果可以拦截，有两种选择：拦截或不拦截，若不可以拦截，就只有不拦截一种选择了。加个记忆化，很好写啊！（好吧，本质上还是最长不上升子序列，只不过换了一种说法）。

第二问也不难，先开一台系统，看是否可以拦截接下来这枚导弹，如果能，就更新高度；如果不能，就新开一台系统。如果有多台系统可以拦截，选高度最低的那台就可以了。（比dp好理解一点吧？）

啥都不说了，上代码吧！

#include<iostream>
#include<fstream>
#include<algorithm>
#include<string>
#include<sstream>
    using namespace std;
    int w=0,e=0,a[105],d[105],f[105][30005];
int dfs(int x,int y)//dfs，表示在第x枚导弹来时，目前能拦截的导弹高度为y时的最优方案 
{
    if(f[x][y]!=-1) return f[x][y];//记忆化，剪枝 
    if(x==w) return 0;//如果到最后一枚导弹了，结束搜索 
    //如果这一枚导弹可以被拦截，就有拦截和不拦截两种选择，取最大值 
    //否则，只有不拦截这一种选择 
    if(a[x+1]<=y) f[x][y]=max(dfs(x+1,a[x+1])+1,dfs(x+1,y));
             else f[x][y]=dfs(x+1,y); 
    return f[x][y];//返回 
} 
int main()
{
    //此题没有数据个数，搞到我要文件读写...... 
    //freopen("L1020-导弹拦截.in","r",stdin);
    for(int i=0;i<105;i++)//初始化一下，养成良好习惯，能有效防止莫名的TLE哦~
        for(int j=0;j<30005;j++) f[i][j]=-1;
    //P.S:有些题用深搜不初始化会T是因为一但出现结果为0的情况你就挂了 
    while(cin>>a[++w]);//读入 
    w--;//这里-1是因为最后读了一个EOF，要忽略掉 
    cout<<dfs(0,30005)<<endl;//深搜并输出（初始高度肯定要高高的啦） 
    //-------------第二问开始------------- 
    d[++e]=30005;//第一台导弹系统初始高度也要高高的 
    for(int i=1;i<=w;i++)
    {
        int Min=30005,f=0;
        //查找能拦截此枚导弹的，高度最低的系统 
        for(int j=1;j<=e;j++)
            if(d[j]>=a[i]&&d[j]<=Min) 
            {
                Min=d[j];
                f=j;
            }
        if(f!=0) d[f]=a[i];//如果找到了，更新那台系统的高度 
            else d[++e]=a[i];//若找不到，再找一台 
    } 
    cout<<e;//输出 
    return 0;
}