首页 > 代码库 > POJ 1018 Communication System 题解
POJ 1018 Communication System 题解
本题一看似乎是递归回溯剪枝的方法,我一提交,结果超时。
然后又好像是使用DP,还可能我剪枝不够。
想了很久,无奈忍不住偷看了下提示,发现方法真多,有贪心,DP,有高级剪枝的,还有三分法的,八仙过海各显神通啊。
坏习惯了,没思考够深入就偷看提示了。
幸好及时回头,还不需要看别人的代码了。自己做出来之后,有空看看多种解法的代码也好。
然后我想出自己的思路了,使用贪心,剪枝,DP综合优化下,呵呵,最后程序有点复杂,优化到了16ms,运气好点,或者vector换成原始数组的话,应该可以0MS了。
总体思路就是:
1 利用STL 的set容器记录有多少不同的B值
2 根据不同的B值,用表tbl记录该B值下的最优解
最后比较所有B值下的最优解,得出最终最优解。
下面是优化过的程序,用了不少技巧,加了注释,希望提高参考价值吧。
#include <stdio.h> #include <float.h> #include <limits.h> #include <algorithm> #include <vector> #include <set> using namespace std; const int MAX_N = 101; int N, M; struct BP { int B, P; bool operator<(const BP &b) const { return B < b.B; } }; BP arr[MAX_N][MAX_N]; float DP(set<int> &bset) { for (int i = 0; i < N; i++) { for (int j = arr[i][0].B-1; j > 0 ; j--) { arr[i][j].P = min(arr[i][j].P, arr[i][j+1].P); }//计算结果为当前大于某个B的最小P值,优化下面填表 } vector<int> bvec(bset.begin(), bset.end()); int M = (int)bvec.size(); //总共有多少个不同的B值 vector<vector<int> > tbl(N, vector<int>(M));//记录当前B下的最优P值 vector<int> idx(N, 1); //arr行的当前下标 for (int j = 0; j < M; j++) { for (int i = 0; i < N; i++) { for ( ; idx[i] <= arr[i][0].B; idx[i]++) { if (arr[i][idx[i]].B >= bvec[j]) { tbl[i][j] = arr[i][idx[i]].P; break; } } if (idx[i] > arr[i][0].B)//某行无法选出比B更大的值了 { tbl[0][j] = -1;//做好标志,剪枝 goto out; } } } out:; float ans = 0.0f; for (int j = 0; j < M && tbl[0][j] != -1; j++) { int totalP = 0; for (int i = 0; i < N; i++) { totalP += tbl[i][j]; } ans = max(ans, float(bvec[j])/float(totalP)); } return ans; } int main() { int T; scanf("%d", &T); while (T--) { scanf("%d", &N); set<int> bset; for (int i = 0; i < N; i++) { scanf("%d", &arr[i][0].B); //记录当前维长度 for (int j = 1; j <= arr[i][0].B; j++) { scanf("%d %d", &arr[i][j].B, &arr[i][j].P); bset.insert(arr[i][j].B);//记录有多少个不同的B值 } sort(arr[i]+1, arr[i]+arr[i][0].B+1);//每维按B值由小到大排序 } printf("%.3f\n", DP(bset)); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。