HDU 4562守護アテナ(dp)

アテナを守る
Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 324    Accepted Submission(s): 91
Problem Description
多くのタワーゲームはクラシックな「アテナを守る」ことをモデルにしている.プレイヤーはモンスターが私たちの女神アテナに近づくのを阻止するために様々な防御ツールを構築する必要があります.
ここで、私たちが建てることができる防御ツールは標準的な円形状の防御壁だけで、アテナと怪物の出生点の間に建てられる防御壁の数が多ければ多いほど、勝利の希望は大きくなります.ここで,問題を2次元座標系に簡略化し,アテナの座標を原点(0,0),モンスターの出生点の座標(X,Y)とする.所定の中心座標と半径を持つN個の防御壁はプレイヤーが選択して構築することができるが、すべての円が正接したり交差したりしないことを保証しなければならない.これらのアテナの位置とモンスターの出生点の位置も壁の縁、つまり防御壁の円を表すことはできません.点の面積も壁の厚さも小さく、無視できます.
覚えておいてください.ゲームが始まった後、怪物はどんな軌跡に沿って、最も少ない円形の防御壁を突破することを選んでアテナのそばに来て、1つの防御壁が突破されると、保護作用を失うことになります.だから、あなたの案は十分に優秀でなければなりません.女神を守るために、最良の建設案を見つけましょう.
 
 
Input
第1の動作Tを入力し、T組のテストデータがあることを示す.
各グループのデータは3つの整数N,X,Yで始まり、次のN行の各行は3つの整数Xi,Yi,Riを含み、選択可能な円心が(Xi,Yi)半径がRiの防御壁であることを示す.
[Technical Specification]
1. 1 <= T <= 100
2. 1 <= N <= 1000
3. 1 <= Ri <= 10 000
4.-10,000<=X,Y,Xi,Yi<=10,000、座標は同じではありません
 
 
Output
各グループのデータに対して、まず何番目のグループのデータを出力し、アテナとモンスターの出生点の間で最も間隔を置くことができる防御壁の数を出力します.
 
 
Sample Input
3 1 5 5 1 0 2 1 5 5 1 0 9 3 5 5 1 0 2 4 5 2 2 0 6
 
 
Sample Output
Case 1: 1 Case 2: 0 Case 3: 2
 
 
Source
2013金山西山居クリエイティブゲームプログラム挑戦試合-再試合(2)
 
 
Recommend
liuyiding
 
 
 
ずっと前からやっていたこの問題は、考えが正しい.一つの場所を間違えて、今日やっと間違いを見つけた.
 
まず2つの点をそれぞれ含む円を探し出して、それからDPは解きます
 

//============================================================================

// Name        : B.cpp

// Author      : 

// Version     :

// Copyright   : Your copyright notice

// Description : Hello World in C++, Ansi-style

//============================================================================



#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <map>

#include <vector>

#include <set>

#include <queue>

#include <string>

#include <math.h>

using namespace std;



const int MAXN=1010;

struct Node

{

    int x,y;

    int r;

};

bool cmp(Node a,Node b)

{

    return a.r<b.r;

}

int dis2(Node a,Node b)

{

    return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

Node node[MAXN];

Node node1[MAXN];

Node node2[MAXN];

int dp1[MAXN];

int dp2[MAXN];

int main()

{

//    freopen("in.txt","r",stdin);

//    freopen("out.txt","w",stdout);

    int T;

    int n;

    int iCase=0;

    Node st;

    st.x=0;st.y=0;

    Node ed;

    scanf("%d",&T);

    while(T--)

    {

        iCase++;

        printf("Case %d: ",iCase);

        scanf("%d",&n);

        scanf("%d%d",&ed.x,&ed.y);

        int t1=0;

        int t2=0;

        for(int i=0;i<n;i++)

        {

            scanf("%d%d%d",&node[i].x,&node[i].y,&node[i].r);

            int d1=dis2(st,node[i]);

            int d2=dis2(ed,node[i]);

            if(d1==node[i].r*node[i].r||d2==node[i].r*node[i].r)

                continue;

            if(d1<node[i].r*node[i].r&&d2<node[i].r*node[i].r)continue;

            if(d1>node[i].r*node[i].r&&d2>node[i].r*node[i].r)continue;

            if(d1<node[i].r*node[i].r)

            {

                node1[t1++]=node[i];

            }

            else node2[t2++]=node[i];

        }

        sort(node1,node1+t1,cmp);

        sort(node2,node2+t2,cmp);

        int ans1=0,ans2=0;

        for(int i=0;i<t1;i++)

        {

            dp1[i]=1;

            for(int j=0;j<i;j++)

            {

                int d=dis2(node1[i],node1[j]);

                if(node1[i].r>node1[j].r && d<(node1[i].r-node1[j].r)*(node1[i].r-node1[j].r))

                    dp1[i]=max(dp1[i],dp1[j]+1);

            }

            ans1=max(ans1,dp1[i]);

        }

        for(int i=0;i<t2;i++)

        {

            dp2[i]=1;

            for(int j=0;j<i;j++)

            {

                int d=dis2(node2[i],node2[j]);

                if( node2[i].r>node2[j].r && d<(node2[i].r-node2[j].r)*(node2[i].r-node2[j].r))

                    dp2[i]=max(dp2[i],dp2[j]+1);

            }

            ans2=max(ans2,dp2[i]);

        }

        int ans=max(ans1,ans2);

        for(int i=0;i<t1;i++)

            for(int j=0;j<t2;j++)

            {

                int d1=dis2(node1[i],node2[j]);

                if(d1>(node1[i].r+node2[j].r)*(node1[i].r+node2[j].r))

                    ans=max(ans,dp1[i]+dp2[j]);

            }

        printf("%d
",ans);

    }



    return 0;

}