NOIP 历年DP贪心题

发表于 | 更新于 | 阅读次数：
本文字数： 810 字 | 阅读时长 ≈ 3 分钟

马上要CSP了，赶快来做点真题。做真题时发现，我要么不会推$DP$，要么贪心贪错。

  1. 洛谷1158 NOIP2010 导弹拦截

我太蕉♂急了，看到这题的第一反应：对于每个点，去找最近的系统管。

刷刷写出代码，信心满满的交上去，完美的只有$40$分。去看了一下讨论，讨论区里有一个和我一样只有$40$分的。和我的做法一样。

然后我来讲一下这个算法为什么不对，顺便提醒一下大家，在做$CSP/NOIP$的贪心题时，一定要van♂分小心。

是这样的：有一些点，如果每个就近选，就会用更多的系统，导致答案分散，用大量的花费完成少量的任务。更优的解法是，一个系统虽然花费的更多，但是一次珂以管理更多导弹。

这句话有点难懂，但是看图就明白了。

blog1.jpg

图中，$A,B$是拦截系统，$C,D$是两个导弹。

然后按照刚刚的“就近原则”，应该是$A$管理$C$，$B$管理$D$。但是这样的花费是$20+37=57$。

实际上，只要$B$管理$D$就足够了。这样的花费是$37$。

这种算法失败的原因，就是因为把原本一个系统就能解决的事情，交给了两个系统。

那么正确的算法又是什么呢。

首先，导弹显然是无序的，根据常年经验和数据我们意识到要排序。

然后我们意识到，我们要把这些导弹分成两个部分，不一定非空，一部分给$A$管，部分给$B$管。

然后我们灵机一动，我们按照到$A$的距离排序，然后一个前缀给$A$，除此之外的部分（一个后缀）给$B$。

然后枚举断点找最小即珂。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 155555
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)

    struct node{int x,y;}a[N];
    int n;
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Input()
    {
        R1(a[1].x),R1(a[1].y),R1(a[2].x),R1(a[2].y);
        R1(n);
        F(i,3,n+2) R1(a[i].x),R1(a[i].y);
    }

    int dis2(node a,node b)
    {
        return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
    }
    bool cmp(node x,node y)
    {
        return dis2(x,a[1])<dis2(y,a[1]);
    }
    int dis[N];
    void Soviet()
    {
        sort(a+3,a+n+3,cmp);
        D(i,n+2,3)
        {
            dis[i]=max(dis[i+1],dis2(a[i],a[2]));
        }

        int ans=0x7f7f7f7f;
        F(i,3,n+2)
        {
            int r1=dis2(a[i],a[1]);
            int r2=dis[i+1];
            ans=min(ans,r1+r2);
        }
        printf("%d\n",ans);
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}

w