首页 > ACM题库 > HDU-杭电 > hdu 2798 Cai In-DFS-[解题报告]hoj
2014
02-14

hdu 2798 Cai In-DFS-[解题报告]hoj

Cai In

问题描述 :

Hero Goblin Techies in DOTA have two skills: Remote Mines – Plants a powerful mine that only detonates when triggered and Detonate – Detonates all remote mines at the same time.
A mine with power A will demage enemy r away from it 1000 * A / (r * r). And when all mines detonate at the same time, the demage to an enemy is the maximum of all the mines, that is maximus of 1000 * A[i] / (r[i] * r[i]).

Goblin Techies has plant many mines in the map, and Panda want to pass the dangerous region.
The region is square, with each side of length 100.0. The coordinate of the southwest corner is (x = 0, y = 0) and the coordinate of the northeast corner is (x = 100, y = 100).
The Panda will enter at (50, 0) and exit at (50, 100), and won’t go out of the region in any other way.

Given the coordinates and powers of all mines in the region, what shound the Panda’s HP be at least if Panda want to pass the region before he died? Assume Panda will choose the best path.

输入:

Each case have four lines. The first line are n integers x[i], the second line are n integers y[i], the third line are n integers A[i], the last line is an empty line. 1 <= n <= 55.

输出:

Each case have four lines. The first line are n integers x[i], the second line are n integers y[i], the third line are n integers A[i], the last line is an empty line. 1 <= n <= 55.

样例输入:

50
2
87

20 50 70
50 70 80
42 42 42

10 10 10 20 30 40 50 60 40 50 60 70 80 80 80 90 90 90
40 50 60 60 60 60 60 70 30 30 30 30 40 30 20 50 40 10
90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90

样例输出:

21750.000
105.000
400.000


题目描述:在魔兽争霸里有一个地精工程师,他可以在一个100*100的区域里埋雷,最多55个,然后这些雷同时爆炸,每一个雷都有一个系数A和它的坐标,对于距离该雷距离为R处的人的伤害是A*1000/(R*R),人受到的伤害是所有雷当中在该处伤害的最大值。然后熊猫要从点(50,0)处进入到该区域,然后从(50,100)处离开该区域,不能在其他的地方走出该区域,问熊猫选择最优路线,那么他至少要有多少的血量。解题报告:这个似乎很好解决,理论AC确实不难。解法无非就是把线段[(50,0),(50,100)]左侧的正方形边界上的点看成一个点为起点S,把线段[(50,0),(50,100)]右侧的正方形边界上的点看成一个点为终点T,然后我们来二分熊猫的血量值K,当血量值为K时那么每一个雷的区域的半径r就是确定的了,那么如果一个雷和另一个雷的区域有交集就在他们之间连边,如果一个雷和正方形的边界有交集就将该雷和S或T连边,然后判断是否可以从S走到T,如果可以那么这个血量上限就是不够的,应该继续增加,否则减少。原来还以为熊猫的血量在求完之后要上取整,WA了很多次,后来却掉了就AC了。代码:/*Name: HDU 2798 Cai InCopyright: happy457Author: happy457Date: 25-10-10 08:26Description: */#include<iostream>#include<algorithm>#include<math.h>#include<string.h>using namespace std;const double eps = 1e-6;struct point{double x,y;double A;double r;};point p[100];int N;bool map[100][100];char str[1000000];inline void getNum(int &i,double &x,int len){x = 0;while((str[i]==’ ‘||str[i]==’\n’)&&i<len) i++;while(str[i]>=’0′&&str[i]<=’9′&&i<len){x = x*10 + str[i] – ’0′;i ++ ;}return;}bool readIn(){if(gets(str)==NULL)return false;int len = strlen(str);int i , j;N = 1;for(i=0;i<len;){getNum(i,p[N].x,len);N++;    }gets(str);len = strlen(str);for(i=0,j=1;i<len;){getNum(i,p[j].y,len);j++;}gets(str);len = strlen(str);for(i=0,j=1;i<len;){getNum(i,p[j].A,len);p[j].A*=1000.0;j++;}gets(str);N–;return true;}double dis(point a,point b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}bool can_reach[110];void dfs(int x){can_reach[x] = true;for(int i=1;i<=N+1&&!can_reach[N+1];i++){if(map[x][i]&&!can_reach[i]){dfs(i);    }}return;}bool check(double mid){int S = 0 , T = N + 1;point s , t;s.x = 50 , s.y = 0;t.x = 50 , t.y = 100;for(int i=1;i<=N;i++){p[i].r = sqrt(p[i].A/mid);double d = dis(p[i],s);if(d<p[i].r) return false;d = dis(p[i],t);if(d<p[i].r) return false;}memset(map,false,sizeof(map));for(int i=1;i<=N;i++){if(p[i].x<=p[i].r) map[S][i] = true;if(p[i].x+p[i].r>=100.0) map[i][T] = true;if(p[i].y<=p[i].r){if(p[i].x<=50) map[S][i] = true;if(p[i].x>=50) map[i][T] = true;}if(p[i].y+p[i].r>=100.0){if(p[i].x<=50) map[S][i] = true;if(p[i].x>=50) map[i][T] = true;}}for(int i=1;i<=N;i++){for(int j=i+1;j<=N;j++){if(dis(p[i],p[j])<p[i].r+p[j].r){map[i][j]=map[j][i]=true;    }}    }memset(can_reach,false,sizeof(can_reach));dfs(S);return !can_reach[T];}double Solve(){double ans = 0 , l = 0 , r = 1e15 , mid;while(r – l >= eps){mid  = (l + r) / 2.0;if(check(mid))    r = mid , ans = mid;else l = mid;}return ans;}int main(){while(readIn()){printf("%.3lf\n",Solve());}}
解题参考:http://hi.baidu.com/happy457/item/e3f40c19732dd88188a956f5


  1. if(j){
    int ans=a ;
    for(int x=j-1;x>=0;x–){
    if(!a ) break;
    ans=min(ans,a );
    sum+=ans;
    }
    }
    求解释,,dp的思路是什么呢?

  2. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。