0.500 0.800 0.800 0.800 0.500

题意：告诉你5个敌人的位置以及他们各自的血量，你有n次机会选择距离和你小于等于d且未被杀死的敌人进行攻击，一开始先选择一个敌人进行攻击，这次攻击不算在n次攻击里面的，然后问你最后每个敌人被杀死的概率。这题网上竟搜不到题解，写了很久才写对。。

思路：开一个8维的dp，用dp[pos][shengyu][t1][t2][t3][t4][t5][idx]表示现在在第i个人身上，还剩几次打击机会，每个人剩余的血量这个状态下继续搜下去杀死每个人所加的概率。

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<string>

#include<algorithm>

using namespace std;

typedef long long ll;

#define inf 99999999

#define maxn 150

struct node{

    int x,y;

}a[10];

int g[10][10];

int n,m;

double dp[5][26][6][6][6][6][6][6];

double ans[5];

int cas;

void init()

{

    int i,j;

    for(i=0;i<5;i++){

        for(j=0;j<5;j++){

            if((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)<=m*m  )g[i][j]=1;

            else g[i][j]=0;

        }

    }

}

void dfs(int pos,int shengyu,int t[],double p)

{

    int i,j;

    if(dp[pos][shengyu][t[0] ][t[1] ][t[2] ][t[3] ][t[4] ][5]==cas){

        for(i=0;i<5;i++){

            ans[i]+=dp[pos][shengyu][t[0] ][t[1] ][t[2] ][t[3] ][t[4] ][i]*p;

        }

        return;

    }

    if(shengyu==0){

        for(i=0;i<5;i++){

            if(t[i]==0){

                dp[pos][shengyu][t[0] ][t[1] ][t[2] ][t[3] ][t[4] ][i]=1;

                ans[i]+=p;

            }

            else{

                dp[pos][shengyu][t[0] ][t[1] ][t[2] ][t[3] ][t[4] ][i]=0;

            }

        }

        dp[pos][shengyu][t[0] ][t[1] ][t[2] ][t[3] ][t[4] ][5]=cas;

        return;

    }

    int cnt=0;

    for(i=0;i<5;i++){

        if(pos!=i && t[i] && g[pos][i])cnt++;

    }

    if(cnt==0){

        for(i=0;i<5;i++){

            if(t[i]==0){

                dp[pos][shengyu][t[0] ][t[1] ][t[2] ][t[3] ][t[4] ][i]=1;

                ans[i]+=p;

            }

            else{

                dp[pos][shengyu][t[0] ][t[1] ][t[2] ][t[3] ][t[4] ][i]=0;

            }

        }

        dp[pos][shengyu][t[0] ][t[1] ][t[2] ][t[3] ][t[4] ][5]=cas;

        return;

    }

    double c[10];

    for(i=0;i<5;i++)c[i]=ans[i];

    for(i=0;i<5;i++){

        if(i!=pos && t[i] && g[pos][i]){

            t[i]--;

            dfs(i,shengyu-1,t,p/(cnt*1.0) );

            t[i]++;

        }

    }

    dp[pos][shengyu][t[0] ][t[1] ][t[2] ][t[3] ][t[4] ][5]=cas;

    for(i=0;i<5;i++)dp[pos][shengyu][t[0] ][t[1] ][t[2] ][t[3] ][t[4] ][i]=(ans[i]-c[i])/p;

}

int main()

{

    int i,j,k,t,h,kk,qq,q;

    int b[10];

    cas=0;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        memset(ans,0,sizeof(ans));

        cas++;

        for(i=0;i<5;i++){

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

        }

        for(i=0;i<5;i++){

            scanf("%d",&b[i]);

        }

        init();

        for(i=0;i<5;i++){

            b[i]--;

            dfs(i,n,b,0.2);

            b[i]++;

        }

        printf("%.3f %.3f %.3f %.3f %.3f\n",ans[0],ans[1],ans[2],ans[3],ans[4]);

    }

    return 0;

}

/*

3 100

0 1 0 2 0 3 0 4 0 5

3 4 2 1 5

0.000 0.000 0.145 0.663 0.000

4 100

0 1 0 2 0 3 0 4 0 5

3 3 3 1 1

0.015 0.015 0.015 0.784 0.784

*/