题意：当任意两个卫星的距离小于等于25时，放置一个天线就可以同时接受到这两个卫星的信号。现在告诉n个卫星的位置，求最少需购买天线数量，同时需要保证，得到的信号值总和最大。信号值计算公式是Qx=100-|卫星的位置-天线的位置|。
分析：只要弄清楚了题意，就很容易发现这个题其实就是经典的村庄里建邮局的问题了，只不过这里要求每一段的范围在25以内。因为数据范围只有100，就没写什么优化了，直接上n^3的。
f[i][j]表示前i个卫星放j个天线所能得到的最大信号。 f[i][j]=max{f[k][j-1]+w[k+1][i]; | d[i]-d[k+1]<=25}
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <algorithm>
using namespace std;
#define eps 1e-8

int n;
double f[110][110],w[110][110],d[110];

int main()
{
    int i,j,k,tem;
    while(scanf("%d",&n)!=EOF)
    {
        d[0]=0.0;
        for(i=1;i<=n;i++) 
        {
            scanf("%lf",&d[i]);
        }
        sort(d+1,d+n+1);
        for(i=1;i<=n;i++)   // 预处理出任意一段放一个卫星的所获得的最大信号值。
        {
            w[i][i]=100.0;
            for(j=i+1;j<=n;j++)
            {
                tem=i+(j-i+1)/2;
                w[i][j]=0.0;
                for(k=i;k<=tem;k++)
                    w[i][j]+=d[tem]-d[k];
                for(;k<=j;k++)
                    w[i][j]+=d[k]-d[tem];
                w[i][j]=(j-i+1)*100.0-w[i][j];
            }
        }
        for(i=0;i<=n;i++)
        {
            for(j=0;j<=n;j++) f[i][j]=-1.0;
        }
        f[0][0]=0.0;
        f[1][1]=100.0;
        for(i=2;i<=n;i++)
        {
            for(j=1;j<=i;j++)
            {
                for(k=i-1;k>=j-1&&d[i]+eps<=25.0+d[k+1];k--)
                {
                    if(f[k][j-1]+eps<0.0) continue; 
                    tem=i-k;
                    if(f[k][j-1]+w[k+1][i]>f[i][j]+eps)
                        f[i][j]=f[k][j-1]+w[k+1][i];
                }
            }
        }
        for(j=1;j<=n;j++)
        {
            if(f[n][j]>=0) break;
        }
        printf("%d %.2lf\n",j,f[n][j]);
    }
    return 0;
}