首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。