动态规划写导弹拦截，c或者c+。老师要求把代码搞到100行并且加注释。

贝球球圆滚滚2018.05.28回答我讲下我的思路这道题首先要明确所有导弹不是被1号系统拦截就是被2号系统拦截我们看到这道题的数据范围是10的5次方，大概是nlogn复杂度，联想到sort排序让我们思考一下最优解，在最优解中1号系统肯定先拦下距离自己近的如果1号去拦距离它远的导弹的话，其实就捎带脚的把近的导弹拦截了如果我们把所有导弹按照对1号的距离进行升序排序，通过刚才的思考我们知道肯定是1号拦截一个前缀，剩下的后缀交给2号那么我们枚举一下这个前缀和后缀的分界点即可（分界点我们此处定义为前缀的最后一个点）前缀处理的1号系统代价比较好算，就是分界点到1号系统的距离2号系统此时就不能再排序看后缀谁是最大的来计算代价，此时需要我们预处理出来一个数组，让d[i]=包括第i以及它后面的导弹中最远距离（思路来源于我的老师）以下是AC题解#include<iostream>#include<algorithm>//sort必须调用的库usingnamespacestd;intx1,y1,x2,y2,n;//输入的五个数，为了cmp函数方便使用，开成全局变量intd[100007];//预处理出来d数组，具体用途请看思路structnode{intx;//记录导弹的位置信息inty;}w[100007];boolcmp(nodea,nodeb){intq=(x1-a.x)*(x1-a.x)+(y1-a.y)*(y1-a.y);intp=(x1-b.x)*(x1-b.x)+(y1-b.y)*(y1-b.y);return(q<p);}intmain(){intans=0;cin>>x1>>y1>>x2>>y2;cin>>n;for(inti=0;i<n;i++){cin>>w[i].x>>w[i].y;}sort(w,w+n,cmp);for(inti=n-1;i>=0;i--){inth=(x2-w[i].x)*(x2-w[i].x)+(y2-w[i].y)*(y2-w[i].y);//预处理过程d[i]=max(d[i+1],h);}ans=d[0];for(inti=0;i<n;i++){intcnt=0;cnt=(x1-w[i].x)*(x1-w[i].x)+(y1-w[i].y)*(y1-w[i].y);cnt+=d[i+1];//由于d[i]所保留的最大值包括i，而此时i属于前缀ans=min(ans,cnt);}ans=min(ans,d[0]);cout<<ans;return0;}