POJ 1018 【动态规划】

【POJ 1018】

题意：有n种设备，每种设备由不同厂家生产的带宽和价格不同。要求每一种设备从其中一个厂家中采购，要求n台设备中的最小带宽B和总价格P的比值B/P最大。
解法：原问题比较难入手，考虑将问题转化为求前i台设备中带宽为j的最小总价格。

设前i台设备中带宽为j的最小价格和为dp[i][j]，k为i-1台设备中的最小带宽，则有
当j<=k时，dp[i][j]=min{dp[i][j],dp[i-1][k]+p[i][j]}
当j>k时，dp[i][k]=min{dp[i][k],dp[i-1][k]+p[i][j]}

利用上述递推式求出dp[n][m]之后，求m/dp[n][m]的最大值，即为答案。

下面是代码：

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<set>
using namespace std;const int MAXN=105;
const int INF=0x3f3f3f3f;
vector<int> B[MAXN];
vector<int> P[MAXN];
vector<int> temp;
set<int> temp2;int dp[MAXN][1200];int main()
{
    int t;scanf("%d",&t);while(t--){
    int n;scanf("%d",&n);for(int i=0;i<=n;i++){
    B[i].clear();P[i].clear();}temp.clear();temp2.clear();int num;for(int i=1;i<=n;i++){
    scanf("%d",&num);int a,b;for(int j=0;j<num;j++){
    scanf("%d%d",&a,&b);B[i].push_back(a);P[i].push_back(b);}}for(int i=0;i<MAXN;i++){
    for(int j=0;j<1200;j++){
    dp[i][j]=INF;}}for(int i=0;i<B[1].size();i++){
    temp.push_back(B[1][i]);dp[1][B[1][i]]=P[1][i];}for(int i=2;i<=n;i++){
    for(int j=0;j<B[i].size();j++){
    for(int k=0;k<temp.size();k++){
    if(B[i][j]>temp[k]){
    dp[i][temp[k]]=min(dp[i][temp[k]],dp[i-1][temp[k]]+P[i][j]);temp2.insert(temp[k]);}else{
    dp[i][B[i][j]]=min(dp[i][B[i][j]],dp[i-1][temp[k]]+P[i][j]);temp2.insert(B[i][j]);}}}temp.assign(temp2.begin(),temp2.end());temp2.clear();}double ans=0;for(int i=0;i<temp.size();i++){
    //cout<<temp[i]<<" "<<dp[n][temp[i]]<<endl;ans=max(ans,temp[i]/(dp[n][temp[i]]*1.0));}printf("%.3f\n",ans);}return 0;
}

测试样例：

Input:
3
3
3 4 1 2 2 3 3
2 2 3 2 4
1 1 4
3
3 100 25 150 35 80 25
2 120 80 155 40
2 100 100 120 110
2
3 1 2 3 4 5 6
2 3 5 4 6
Output:
0.125
0.649
0.333