首页 > 代码库 > UVALive 4731 Cellular Network

UVALive 4731 Cellular Network

题解:

也是比较简单的DP,

贪心不难想到,大的肯定在前面最好。从大到小排序,dp[i][j] 表示前i个数分为j组

dp[i][j] = min( dp[k][j - 1], i * (sum[i] -sum[k]) );

注意精度问题。不要一开始就算。只需要最后除以sum即可

代码:

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define se second
#define fs first
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define pii pair<int,int>
const int INF = 1000000000;
const int maxn = 105;
const int M = 4000;

int a[ maxn ], sum[ maxn ];
int dp[ maxn ][ maxn ];
int n, m;

int main()
{
    int T;
    scanf( "%d", &T );
    while( T -- )
    {
        scanf( "%d%d", &n, &m );
        for( int i = 1; i <= n; i ++ ) scanf( "%d", &a[ i ] );
        sort( a + 1, a + n + 1, greater< int >() );
        for( int i = 1; i <= n; i ++ ) sum[ i ] = sum[ i - 1 ] + a[ i ];
        for( int i = 1; i <= n; i ++ ) dp[ i ][ 1 ] = i * sum[ i ];
        for( int i = 2; i <= m; i ++ )
        for( int j = i; j <= n; j ++ )
        {
            dp[ j ][ i ] = INF;
            for( int k = i - 1; k <= j - 1; k ++ )
            dp[ j ][ i ] = min( dp[ j ][ i ], dp[ k ][ i - 1 ] + j * ( sum[ j ] - sum[ k ] ) );
        }
        printf( "%.4lf\n",( double )dp[ n ][ m ] / ( double )sum[ n ] );
    }
    return 0;
}

 

UVALive 4731 Cellular Network