首页 > 代码库 > ZOJ 1409 communication system 双变量型的DP
ZOJ 1409 communication system 双变量型的DP
这个题目一开始不知道如何下手，感觉很像背包，里面有两个变量，一个带宽B，一个价格P，有n个设备，每个设备有k个可选的器材（只需选一个），每个器材都有自己的B和P，
n个设备选n个器材，最终，FB=所有器材里最小的B，FP=总的价格，要使得FB/FP最大
这种题目得先把一个变量给控制起来，或者说枚举其中一个变量之后，再通过dp的方法得到另一个变量的最优值，千万别想一步登天
像这个题目，我们如果先把每个设备对应的器材按价格升序排序，然后我枚举可能的FB，对于每个设备，我从前往后扫，一旦扫到了B>=FB(合法数据)，就停止，取该值，最后扫完整个n个设备，得到的值必定是我枚举 的FB对应的最大FB/FP，这个显而易见嘛。。因为数据量不大，所以可以用。当然我算了下峰值的复杂度可以达到10的8次方，但是其实达不到，其中很难每个循环都运行完。
其实这样看来倒不像DP了，其实是暴力枚举了
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <vector>using namespace std;struct node{ int b,v; bool operator < (const node&rhs) const{ return v<rhs.v; }};vector<node>G[110];int B[10010];int n,cnt;int main(){ int t; scanf("%d",&t); while (t--) { cnt=0; scanf("%d",&n); for (int i=0;i<=n;i++) G[i].clear(); for (int i=1;i<=n;i++){ int k,a,b; scanf("%d",&k); while (k--){ scanf("%d%d",&a,&b); B[cnt++]=a; G[i].push_back((node){a,b}); } sort(G[i].begin(),G[i].end()); } sort(B,B+cnt); int m=0; for (int i=1;i<cnt;i++){ if (B[i]!=B[i-1]) B[++m]=B[i]; } double ans=0.0; for (int i=0;i<=m;i++){ bool flag=1; double sum=0; for (int j=1;j<=n && flag;j++){ int r=G[j].size(); for (int k=0;k<r;k++){ if (G[j][k].b>=B[i]){ sum+=(double)G[j][k].v; break; } if (k==r-1 && G[j][k].b<B[i])flag=0; } } if (!flag) continue; ans=max(ans,(double)B[i]*1.0/sum); } printf("%.3f\n",ans); } return 0;}
ZOJ 1409 communication system 双变量型的DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。