hdu 4562 dp ***

题意：给出一个点p(X,Y)以及若干圆。从中选出尽可能多的圆满足：圆能且只能包含p或者原点中的一个（不能在圆上）；圆之间不能相交或者相切。

链接：点我

用dp求满足条件包含一个点圆的最多数目，然后两个点再求最大的即可

思路：首先分理出只包含原点或者p的圆，然后分别按照半径升序排序。分别对包含原点和p的进行dp。f1[i]表示包含原点的圆中前i个最多选出多少个。f2[i]表示p的。然后合并。就是枚举 f1的i和f2的j，若这两个圆不冲突，那么就能选出f1[i]+f2[j]个。

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<queue>
  7 #include<map>
  8 using namespace std;
  9 #define MOD 1000000007
 10 #define pb(a) push_back(a)
 11 const int INF=0x3f3f3f3f;
 12 const double eps=1e-5;
 13 typedef long long ll;
 14 #define cl(a) memset(a,0,sizeof(a))
 15 #define ts printf("*****
");
 16 const int MAXN=1010;
 17 int dp1[MAXN],dp2[MAXN];
 18 int n,m,tt,cnt;
 19 struct Node
 20 {
 21     int x,y;
 22     int r;
 23     void in()
 24     {
 25         scanf("%d%d%d",&x,&y,&r);
 26     }
 27 }st,ed,node[MAXN],node1[MAXN],node2[MAXN];
 28 int dis(Node a,Node b)
 29 {
 30     return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
 31 }
 32 bool cmp(Node a,Node b)
 33 {
 34     return a.r<b.r;
 35 }
 36 int main()
 37 {
 38     int i,j,k;
 39     #ifndef ONLINE_JUDGE
 40     freopen("1.in","r",stdin);
 41     #endif
 42     int ca=1;
 43     scanf("%d",&tt);
 44     int X,Y;
 45     st.x=0,st.y=0;
 46     while(tt--)
 47     {
 48         scanf("%d%d%d",&n,&X,&Y);
 49         ed.x=X,ed.y=Y;
 50         int tot1=0,tot2=0;
 51         for(i=0;i<n;i++)
 52         {
 53             node[i].in();
 54             int d1=dis(st,node[i]);
 55             int d2=dis(ed,node[i]);
 56             if(d1==node[i].r*node[i].r||d2==node[i].r*node[i].r)  continue;  //点在圆上
 57             if(d1>node[i].r*node[i].r&&d2>node[i].r*node[i].r)    continue;   //不包含任何点
 58             if((d1<node[i].r*node[i].r)&&(d2<node[i].r*node[i].r))   continue;   //两个点都包含
 59             if(d1<node[i].r*node[i].r)
 60             {
 61                 node1[tot1++]=node[i];
 62             }
 63             else    node2[tot2++]=node[i];
 64         }
 65         cl(dp1);
 66         cl(dp2);
 67         sort(node1,node1+tot1,cmp);
 68         sort(node2,node2+tot2,cmp);
 69         int ans1=0,ans2=0;
 70         for(i=0;i<tot1;i++)
 71         {
 72             dp1[i]=1;
 73             for(j=0;j<i;j++)
 74             {
 75                 if(node1[i].r==node1[j].r)    continue;
 76                 int d=dis(node1[i],node1[j]);
 77                 if(d<(node1[i].r-node1[j].r)*(node1[i].r-node1[j].r))
 78                 {
 79                     dp1[i]=max(dp1[i],dp1[j]+1);
 80                 }
 81             }
 82             ans1=max(ans1,dp1[i]);
 83         }
 84         for(i=0;i<tot2;i++)
 85         {
 86             dp2[i]=1;
 87             for(j=0;j<i;j++)
 88             {
 89                 if(node2[i].r==node2[j].r)    continue;
 90                 int d=dis(node2[i],node2[j]);
 91                 if(d<(node2[i].r-node2[j].r)*(node2[i].r-node2[j].r))
 92                 {
 93                     dp2[i]=max(dp2[i],dp2[j]+1);
 94                 }
 95             }
 96             ans2=max(ans2,dp2[i]);
 97         }
 98         int ans=max(ans1,ans2);
 99         for(i=0;i<tot1;i++)
100         {
101             for(j=0;j<tot2;j++)
102             {
103                 int d=dis(node1[i],node2[j]);
104                 if(d>(node1[i].r+node2[j].r)*(node1[i].r+node2[j].r))
105                     ans=max(ans,dp1[i]+dp2[j]);
106             }
107         }
108         printf("Case %d: %d
",ca++,ans);
109     }
110 }