HDU-4562

2018-03-11

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=4562

题目大意

给定两个点，(0,0)和(x,y)，求两点之间最多画多少个圆，要求两个圆之间不相交不相切。
具体的实际意义需要考虑。

思想

首先因为怪兽的路径是任意的，所以如果防御圈同时包含爱丽丝和怪兽，或者同时不包含爱丽丝和怪兽，那么这个包围圈就是没有意义的。所以有意义的包围圈只有两种情况：只包含爱丽丝和只包含怪兽。所以先处理出来这两个圈。
然后分别对两种圈DP，DP的思路很简单，不过有一个处理很关键，就是要按照r排序。从小到大DP。
最后把两个圈综合起来即可。

注意，注释里的代码是我的错误代码，不过还没想明白怎么错。。

代码

HDU-4562

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
struct circle{
    int x;
    int y;
    int r;
}master[1050],athena[1050];
int master_num,athena_num;
int dp1[1050],dp2[1050];
bool cmp(circle a,circle b)
{
    return a.r<b.r;
}

bool ok(circle a,circle b)
{
    int dis=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
    int r1=a.r+b.r,r2=a.r-b.r;
    if (r2*r2<=dis && dis<=r1*r1) return false;
    return true;
}

int main()
{
    int T;
    scanf("%d",&T);
    for (int TT=1;TT<=T;TT++)
    {
        master_num=0; athena_num=0;
        int N,X,Y;
        scanf("%d%d%d",&N,&X,&Y);
        for (int i=1;i<=N;i++)
        {
            int x,y,r;
            scanf("%d%d%d",&x,&y,&r);
            if ((r*r > x*x+y*y) && (r*r < (x-X)*(x-X)+(y-Y)*(y-Y)))
            {
                athena_num++;
                athena[athena_num].x=x; athena[athena_num].y=y; athena[athena_num].r=r;
            }
            else
            if ((r*r < x*x+y*y) && (r*r > (x-X)*(x-X)+(y-Y)*(y-Y)))
            {
                master_num++;
                master[master_num].x=x; master[master_num].y=y; master[master_num].r=r;
            }
        }
        sort(master+1,master+master_num+1,cmp);
        sort(athena+1,athena+athena_num+1,cmp);
        memset(dp1,0,sizeof(dp1));
        memset(dp2,0,sizeof(dp2));
        for (int i=1;i<=athena_num;i++)
        {
            int mmax=0;
            for (int j=1;j<i;j++)
            {
                if (ok(athena[i],athena[j])) mmax=max(mmax,dp1[j]);
            }
            dp1[i]=mmax+1;
        }
        for (int i=1;i<=master_num;i++)
        {
            int mmax=0;
            for (int j=1;j<i;j++)
            {
                if (ok(master[i],master[j])) mmax=max(mmax,dp2[j]);
            }
            dp2[i]=mmax+1;
        }
        int ans=0;
        /*
        if (athena_num == 0 && master_num != 0)
            for (int i=1;i<=master_num;i++) ans=max(ans,dp2[i]);
        else
            if (athena_num != 0 && master_num == 0)
                for (int i=1;i<=athena_num;i++) ans=max(ans,dp1[i]);
            else
                for (int i=1;i<=athena_num;i++)
                {
                    for (int j=1;j<=master_num;j++)
                    {
                        if (ok(athena[i],master[j]))
                        {
                            ans=max(ans,dp1[i]+dp2[j]);
                        }
                    }
                }
        */
        for (int i=1;i<=master_num;i++) ans=max(ans,dp2[i]);
        for (int i=1;i<=athena_num;i++) ans=max(ans,dp1[i]);
        for (int i=1;i<=athena_num;i++)
        {
            for (int j=1;j<=master_num;j++)
            {
                if (ok(athena[i],master[j]))
                {
                    ans=max(ans,dp1[i]+dp2[j]);
                }
            }
        }
        printf("Case %d: %d\n",TT,ans);
    }
    return 0;
}

后记

DP的思路不难，DP前的各种处理都比较难想。
昨天和今天是堕落的一天。
明天比赛加油。