题意:当任意两个卫星的距离小于等于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.0continue
                    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]>=0break;
        }

        printf(
"%d %.2lf\n",j,f[n][j]);
    }

    
return 0;
}