题目大意:有一个系统,这个系统由n种设备组成,现在每种设备有m个,设备有两种属性
一个是带宽,一个是价格
每种设备取一个,取满n个,怎么才能使所有带宽总和/总价格最大
解题思路:动态规划,dp[i][j]表示取到第i个设备带宽为j的最小的价格
那么有
for i = 1 : n
forj = 0 : MAXV*MAXV
for k = 1 : m
dp[i][min(j,b[k]) = min(dp[i-1][j] + p[k] , dp[i][min(j,b[k]))
好像如果dp[i][j]表示取到第i个价格为j的最大带宽的话,空间会爆掉
#include <iostream> #include <iomanip> using namespace std; #define MAXV 105 #define INF INT_MAX int min(int a,int b){ return a>b?b:a; } int max(int a,int b){ return a<b?b:a; } class CDevice{ public: int m_nPrice; int m_nBandWidth; }; class CComSystem{ public: void Run(); CComSystem(){ m_nDp = new int*[MAXV]; for(int i = 0;i < MAXV;i++){ m_nDp[i] = new int[MAXV*MAXV]; for(int j = 0;j < MAXV*MAXV;j++){ m_nDp[i][j] = INF; } } device = new CDevice[MAXV]; } ~CComSystem(){ for(int i = 0;i < MAXV;i++){ delete []m_nDp[i] ; } delete []m_nDp; delete []device; } private: int **m_nDp; CDevice *device; }; void CComSystem::Run(){ int n, m ,maxBand = 0; int i, j ,k; double ans = -1; cin>>n; for(i = 0;i < n;i++){ cin>>m; for(j = 0;j < m;j++){ cin>>device[j].m_nBandWidth>>device[j].m_nPrice; maxBand = max(maxBand,device[j].m_nBandWidth); } if(i == 0){ for(j = 0;j < m;j++){ m_nDp[i][device[j].m_nBandWidth] = min(device[j].m_nPrice,m_nDp[i][device[j].m_nBandWidth]); } continue; } for(j = 0;j <= maxBand;j++){ if(m_nDp[i - 1][j]!=INF){ for(k = 0;k < m;k++){ m_nDp[i][min(j,device[k].m_nBandWidth)] = min(m_nDp[i - 1][j] + device[k].m_nPrice, m_nDp[i][min(j,device[k].m_nBandWidth)]); } } } } for(j = 0;j < MAXV*MAXV;j++){ if(m_nDp[n - 1][j]!=INF){ if(ans < 1.0*j/m_nDp[n - 1][j]){ ans = 1.0*j/m_nDp[n - 1][j]; } } } // printf("%.3lf\n",ans); cout<<fixed<<setprecision(3)<<ans<<endl; } int main(){ int Case; cin>>Case; while(Case--){ CComSystem com; com.Run(); } return 0; }