本文主要是介绍POJ 1018 Communication System（搜索/贪心/动归），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
点击打开链接
搜索（TLE）：
//poj 1018
//2014-6-10
#include <iostream>
#include <cstdio>
using namespace std;
const int MAX_N = 100;
const int INF = 0x3f3f3f3f;
int n;
struct M
{int b, p;
} m[MAX_N][MAX_N];
int num[MAX_N];double ans = -1;//force search
void search ( int cur , int minB, int sum )
{if ( cur == n ){ans = max ( ans, 1.0 * minB / sum );return;}for ( int j = 0; j < num[cur]; j++ ){int Min = min ( minB, m[cur][j].b );search ( cur + 1, Min, sum + m[cur][j].p );}
}int main()
{//freopen ( "in.txt", "r", stdin );int t;scanf ( "%d", &t );while ( t-- ){ans = -1;scanf ( "%d", &n );for ( int i = 0; i < n; i++ ){scanf ( "%d", &num[i] );for ( int j = 0; j < num[i]; j++ ){scanf ( "%d%d", &m[i][j].b, &m[i][j].p );}}search ( 0, INF, 0 );printf ( "%.3f\n", ans );}return 0;
}贪心法（AC / 47MS)：
从1到Max Bandwidth枚举brandwidth，对于每个manufacturers取最小 price。
int maxb = -1;
void solve()
{//enmu all bandwidthfor ( int b = 1; b <= maxb; b++ ){int sum = 0;for ( int i = 0; i < n; i++ ){int Min = INF;for ( int j = 0; j < num[i]; j++ ){if(m[i][j].b >= b)Min = min ( Min, m[i][j].p );}sum += Min;}ans = max ( ans, 1.0 * b / sum );}
}动归 AC / 16MS（参照别人的= = ，可见我DP有多渣渣）：
dp[i][j] 选择第i个设备时，带宽为j的最小费用。
#include <iostream>
#include <cstdio>
using namespace std;
const int MAX_N = 100;
const int INF = 0x3f3f3f3f;
int n;
struct M
{int b, p;
} m[MAX_N][MAX_N];
int num[MAX_N];int maxb = -1;
int d[MAX_N][1009];
void dp()
{memset ( d, 0x3f, sizeof ( d ) );memset ( d, 0, sizeof ( d[0] ) );for ( int i = 1; i <= n; i++ ){for ( int j = 1; j <= num[i]; j++ ){for ( int k = 1; k <= m[i][j].b; k++ ){d[i][k] = min ( d[i][k], d[i - 1][k] + m[i][j].p );}}}double ans = 0;for ( int i = 1; i <= maxb; i++ ){ans = max ( ans, 1.0 * i / d[n][i] );}printf ( "%.3lf\n", ans );
}int main()
{freopen ( "in.txt", "r", stdin );int t;scanf ( "%d", &t );while ( t-- ){scanf ( "%d", &n );for ( int i = 1; i <= n; i++ ){scanf ( "%d", &num[i] );for ( int j = 1; j <= num[i]; j++ ){scanf ( "%d%d", &m[i][j].b, &m[i][j].p );maxb = max ( maxb, m[i][j].b );}}dp();}return 0;
}
这篇关于POJ 1018 Communication System（搜索/贪心/动归）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
