POJ 1018 Communication System 题解
system poj 题解 Communication
2023-09-11 14:14:09 时间
本题一看似乎是递归回溯剪枝的方法。我一提交,结果超时。
然后又好像是使用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; }
相关文章
- Do not throw System.Exception, System.SystemException, System.NullReferenceException, or System.IndexOutOfRangeException intentionally from your own source code
- System.Windows.Forms中的Message Structure
- C#、.Net代码精简优化(空操作符(??)、as、string.IsNullOrEmpty() 、 string.IsNullOrWhiteSpace()、string.Equals()、System.IO.Path 的用法)
- C#学习记录——System.IO命名空间,文件基本操作
- 【JAVA】system.out.print、System.out.println和System.out.printf输出
- 关于System.Convert那些事
- 当JBOSS遇到System.exit()
- 使用git send-email报:Please install an MTA on this system if you want to use sendmail如何处理?
- 报错:System.NotSupportedException: LINQ to Entities does not recognize the method
- system.DateTime ToDateTime(System.String)”,因此该方法无法转换为存储表达式-解决方法
- 【HDU 4940】Destroy Transportation system(无源无汇带上下界可行流)
- System.setProperty()
- Nullable<System.DateTime>日期格式转换 (转载)
- Executing System commands in Java---ref
- 数据库还原,System.Data.SqlClient.SqlError: 因为数据库正在使用,所以无法获得对数据库的独占访问权。
- java.sql.SQLException: Unknown system variable 'query_cache_size'
- PHP Warning: date() [function.date]: It is not safe to rely on the system's timezone