POJ 1018(dp Or 枚举）
发布时间：2020-12-13 20:11:51 所属栏目：PHP教程 来源：网络整理
导读：Communication System Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 23738 Accepted: 8437 Description We have received an order from Pizoor Communications Inc. for a special communication system. The system consists of several d
|
[Submit] [Go Back] [Status] [Discuss] dp做法，dp[i][j]表示前i个物品最小带宽为j所需的最小费用。 /*************************************************************************
> File Name: xiaozhao.cpp
> Author: acvcla
> QQ:acvcla@gmail.com
> Mail: acvcla@gmail.com
> Created Time: 2014年12月27日 星期1 22时34分13秒
*************************************************************************/
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstdlib>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e2+10;
const int maxv=1e3+10;
int dp[maxn][maxv],b[maxn],p[maxn];
int main()
{
int T,n,m;
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
memset(dp,sizeof dp);
int maxb=0;
for(int i=0;i<n;++i) {
scanf("%d",&m);
for(int j=0;j<m;++j){
scanf("%d%d",&b[j],&p[j]);
maxb=max(maxb,b[j]);
}
if(i==0) {
for(int j=0;j<m;++j) {
if(!dp[0][b[j]])dp[0][b[j]]=p[j];
else dp[0][b[j]]=min(dp[0][b[j]],p[j]);
}
continue;
}
for(int j=1;j<=maxb;j++) if(dp[i⑴][j]) {
for(int k=0;k<m;k++) {
int minb=min(b[k],j);
if(!dp[i][minb])dp[i][minb]=dp[i⑴][j]+p[k];
else dp[i][minb]=min(dp[i][minb],dp[i⑴][j]+p[k]);
}
}
}
double ans=0;
for(int i=1;i<=maxb;i++) {
if(!dp[n⑴][i])continue;
ans=max(ans,1.0*i/dp[n⑴][i]);
}
printf("%.3f
",ans);
}
return 0;
} 枚举竟然比dp更快。。。，枚举最小带宽。
/*************************************************************************
> File Name: xiaozhao.cpp
> Author: acvcla
> QQ:acvcla@gmail.com
> Mail: acvcla@gmail.com
> Created Time: 2014年12月27日 星期1 22时34分13秒
*************************************************************************/
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstdlib>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e4+10;
const int inf=0x3f3f3f3f;
vector<pii>communication[maxn];
vector<int> v;
double work(int x,int n)
{
int b=inf;
double p=0;
for(int i=0;i<n;i++) {
int ch=⑴;
for(int j=0;j<communication[i].size();++j) if(communication[i][j].first>=x) {
if(ch==⑴||communication[i][j].second<communication[i][ch].second||
(communication[i][j].second==communication[i][ch].second&&communication[i][j].first>communication[i][ch].first)){
ch=j;
}
}
if(ch==⑴)return ⑴.0;
b=min(b,communication[i][ch].first);
p+=communication[i][ch].second;
}
return b/p;
}
double solve(int n)
{
sort(v.begin(),v.end());
unique(v.begin(),v.end());
int L=0,R=v.size();
double ans=⑶.0,p=0;
for(int i=0;i<v.size();++i) {
p=work(v[i],n);
if(p<=0)return ans;
ans=max(p,ans);
}
return ans;
}
int main()
{
int T,&n);
for(int i=0;i<n;i++)communication[i].clear();
v.clear();
for(int i=0;i<n;i++) {
scanf("%d",&m);
int b,p;
while(m--) {
scanf("%d%d",&b,&p);
v.push_back(b);
communication[i].push_back(make_pair(b,p));
}
}
printf("%.3f
",solve(n));
}
return 0;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |