怎么都没有人回帖啊？？
大家讨论一下撒，不一定要对的，把自己的想法思路说一下就可以了是撒。。

能不能简化一下题目，我不喜欢看太多文字，拜托！！

@_@

看的云里雾里~~~~~~~~

不会是动态规划吧 或者倒过来递推

不清楚

文字暴多……恶寒~~~~~~~~~~
看得晕阿~~~~~~~摆脱下次楼主大人多少把自己的想法大致理一下，这样就把一大串的文字扔出来很不人道阿`~~~~~~~~
按照题目上的意思，我觉得：
1。炸弹应该尽可能放在可以炸毁敌方最多武器数的地方，因为炸弹可持续爆炸五分钟（问题在于，上题中所说的持续引爆和持续爆炸有无异同？）而敌方武器被炸毁一次后二号炸弹转换状态时间为1秒，即在这1秒内其仍旧处于无敌自卫状态？炸弹引爆（就是想要它炸他就开炸？）不需时间？……
混乱了，最终感想就是那个B国首脑脑子被撞坏了阿~~~耗资百亿元之研制的连环阵（Zenith Protected Linked Hybrid Zone），竟然就是这种废渣……用炸弹竟然就可以摧毁，还让世间多了像这种样子变态的题目，去跳楼算了……

A国先选取一个能炸很多B国武器的炸弹,以这个炸弹为基准,在选择离这个炸弹最远同时炸B国连续武器最多的炸弹,在以此炸弹为基准这样选择下去就可以达到最少需求的目地.

楼上的说清楚一点好不好~~~~~~不明白也~~~~

带个头，算法不是很好，就这个意思

#include <stdio.h>
#include <malloc.h>
#include <math.h>
typedef struct{
    int        x;
    int        y;
}Pos;

typedef struct{
    int        bb;
    int        id;
    Pos        p;
}Bomb;

typedef struct{
    int        dd;
    int        id;
    Pos        p;
}Weapon;

/* declare the function will be used */
int distance(Pos weapon,Pos bomb);
/*
main()
*/
int main(void)
{
    char    result[128];
    int        M,n,k;
    int        deadcnt = 0;
    int        dead = 0;
    int        temp = 0;
    int        i,j,cnt = 0;
    int        count = 0;
    Weapon*    weapon;
    Bomb*    bomb;
    FILE*    fp_out = (FILE*)NULL;
    FILE*    fp_in = (FILE*)NULL;

    result[0] = '\0';
    fp_in = fopen("zplhz.in","r");
    fp_out = fopen("zplhz.out","w");
    
    /* Set pointer to beginning of file: */
    fseek( fp_in, 0L, SEEK_SET );

    /* Read data from input file: */
    fscanf( fp_in, "%d", &M );
    fscanf( fp_in, "%d", &n );
    fscanf( fp_in, "%d", &k );

    weapon = (Weapon *)malloc(M*sizeof(Weapon));
    bomb = (Bomb *)malloc(n*sizeof(Bomb));
    for( i = 0;i < M;i++ ) {
        weapon[i].dd = 0;
        fscanf( fp_in, "%d", &weapon[i].p.x );
        fscanf( fp_in, "%d", &weapon[i].p.y );
    }
    for( i = 0;i < n;i++ ) {
        bomb[i].bb = 0;
        fscanf( fp_in, "%d", &bomb[i].p.x );
        fscanf( fp_in, "%d", &bomb[i].p.y );
    }

    /* Start */
    cnt = 0;
LOOP:
    temp = 0;
    for( i = 0;i < n;i++ ) {
        dead = 0;
        if(bomb[i].bb == 1) continue;

        for( j = deadcnt;j < M;j++ ) {
            if( distance(bomb[i].p,weapon[j].p)<=k*k ) {
                dead++;
            }
            else break;
        }

        if( dead>temp ) {
            cnt = i;
            temp = dead;
        }
    }
    bomb[cnt].bb = 1;
    deadcnt = deadcnt+temp;
    count++;
    sprintf(result,"%s %d",result,cnt+1);
    if(deadcnt != M) goto LOOP;
    
    /* End */
    fprintf(fp_out,"%d\n%s",count,result);
    fclose(fp_in);
    fclose(fp_out);
    printf("result saved in file 'zplhz.out'\n");
}

/*
distance()
*/
int distance(Pos A,Pos B)
{
    int        X,Y;

    X = A.x-B.x;
    Y = A.y-B.y;

    return( X*X+Y*Y );
}

初步分析：
A国炸弹I可以炸到B国武器J的条件: (u[i]-x[j])2+(v[i]-y[j])2<=r2
结论：很难找到求最优解的多项式算法。
面对此类问题，一般只有搜索策略。
进一步分析：
每一颗炸弹必定炸掉B国武器中编号连续的一段。
5分钟只是表明每一颗炸弹可以炸掉任意多个编号连续的B国武器。
部分搜索：
此题使用部分搜索的算法需要一些转化：如果已经将B国武器根据编号分为x
段，[Si,Ti] (S1=1,Ti>=Si,Ti+1=Si+1)。然后判断是否可以从A国的N颗炸弹中选出x
颗，分别可以炸掉其中的一段。
其实我们把搜索分为了两部分，先通过搜索将B国武器根据编号分为x段，再
通过搜索判断是否可以从A国的N颗炸弹中选出x颗，分别可以炸掉其中的一段。
其实第二部分可以用匹配来解决。
C[S][T][I] 表示A国炸弹I是否可以炸到B国武器S,S+1..T-1,T。
C[S][S][I]=((u[I]-x[S])2+(v[I]-y[S])2<=R2)
C[S][T][I]=C[S][T-1][I] & C[T][T][I] (S<T)
求C的时间复杂度为O(N3)。
建图：左边x个点，表示B国武器根据编号分为的x段，右边N个点，表示A国
的N颗炸弹。左边第i个点到右边第j个点有边的条件即：C[Si][Ti][j]。
搜索的任务就是将B国武器根据编号划分为若干段+二分图匹配判断。
性能分析（1）：
搜索的基本框架已经建立，虽然数据是随机生成的，但是M个B国武器的划分
方案还是非常多的，有时可能高达2m。时间上很难承受，如果使用卡时，正确性
受到影响，效果不会很好。
只有4个数据可以在时限内出解，另外6个如果卡时，有1个也可以得到最优
解。
优化：
优化可以通过可行性和最优性两方面分析。
优化一（最优性）：如果A国炸弹可以重复使用，设：
Dist[i]=炸掉B国武器i－m的最少使用炸弹数。可以用动态规划计算Dist值，
状态转移方程如下：
Dist[m+1]=0。
Dist[i]=Min(Dist[j]+1 | Can[i][j-1][k](1<=k<=n)) (1<=i<=n)
(i<j<=n+1)
求Dist的时间复杂度为O(N3)。
从而产生了一个最优性剪枝条件：
if 当前已经使用的炸弹数+Dist[当前已经炸掉的B国武器数+1]>=当前找到
的最优解 then 剪枝；
优化二（可行性）：
此搜索方法一般都可以用两个效果很好的可行性优化：
(1)提前判断是否可以匹配成功，避免多余的搜索。
(2)每次匹配可以从以前的匹配开始扩展，不需要重新开始。
如果当前的划分方法已经无法匹配成功，就没有搜索下去的必要了，只要每
搜索新的一段时立即通过匹配判断即可。
每次求匹配只要从原来的基础上扩展就可以了。
通过上述两个优化，程序的效率有了很大的提高。
性能分析（2）：
虽然通过上述两个优化，程序的效率较原来的搜索有了很大的提高。10个测
试数据中有8个可以在时限内出解，另外2个如果卡时，有1个也可以得到最优解。
进一步优化：
优化二虽然排除了许多不必要的划分，但是在判断时浪费了不少时间。
因此，在枚举划分长度时，可以通过以前的划分和匹配情况（被匹配的边），
用O(n2)的时间复杂度的宽度优先搜索计算出下一个划分的最大长度maxL，显然
下一个划分的长度在[1，maxL]都一定可以找到可行的匹配。这样既节省了判断
的时间，又可以使每次划分长度从长到短枚举，使程序尽快逼近最优解，同时增
强了剪枝条件一的效果。
这一部分的实现，首先需要求MaxT。
MaxT[I][S]=炸弹i，从S开始炸，可以炸到的最大编号。
如果，炸弹i炸不到S，则MaxT[I][S]=S-1。
求MaxT[I][S]可以用动态规划的方法解决。状态转移方程为：
MaxT[I][S]= 炸弹i炸不到S S-1
炸弹i炸得到S MaxT[i][S+1]
MaxT[i][m+1]=m
求MaxT的时间复杂度为O(N2)。
具体实现方法，考虑二分图右边的n个结点（n颗炸弹），如果结点i没有匹配，
i被认为可以使用。对于一个已经匹配的结点i，如果从任何一个没有匹配的结点
出发存在一条到达i，而且i为外点的交错路，i也被认为可以使用。
计算所有从没有匹配点出发的交错路（没有匹配点i出发的交错路没有被匹
配点i一定为外点）所能到达的匹配的结点，只要从每一个没有匹配的结点出发，
宽度优先搜索，只要O(N2)的时间。注意判断重复（如果一个已经匹配的结点已
经被确定为可以使用，那么不需要对它再扩展一次，因为当把这个已经匹配的结
点确定为可以使用的结点的时候，已经从这个结点扩展过，如果再扩展必将产生
无谓的重复）
所以MaxL=Max(MaxT[I][S] | i可以使用)；
性能分析（3）：
通过以上的优化，所有数据都是瞬间出解，并且所有结果都是最优解。
甚至对n=200的随机数据，也可以在瞬间出解，可见程序的效率有了很大的
提高。
精益求精：
另外，还有两个优化，但是有时效果不好，但也值得一提。
优化三：分支定界。这样可以增强剪枝条件一的效果，但是当最优解与
Dist[1]相差比较远的时候，会浪费一定的时间。
优化四：优化一中Dist[i]的值有时并不是最优的，通过测试，发现如果
Dist[i]的值与最优值相差1，特别是当i 小的时候，程序的速度都会有明显的
影响。所以，可以通过同样的搜索来计算Dist[i]，（本题的答案就是Dist[1]）。
这样做可以增强剪枝条件一的效果，但是同时对每个i都要搜索也浪费了一定的
时间。
程序结果比较：
1 2 3 4 5 6 7 8 9 10
最简单的
搜索
0.00 0.00 0.50
Time
Over
0.65
Time
Over
Time
Over
Time
Over
Time
Over
Time
Over
优化的搜
索
0.01 0.01 0.10
Time
Over
0.50 0.80
Time
Over
0.55 0.30 0.80
进一步优
化的搜索
0.01 0.01 0.02 0.03 0.00 0.02 0.02 0.01 0.02 0.02
此搜索方法一般都可以用两个效果很好的可行性优化：
(1)提前判断是否可以成功，避免多余的搜索。
(2)每次判断尽量多利用以前的判断结果。