|
随机化贪心，顾名思义，就是边随机边贪心 这类算法适合解决动态规划类的题目
思想：在贪心原则正确的情况下，随机执行足够多次，就是正解了(涉及到概率学，这里不深究) 不要以为随机到正解几率很小，假设随机到正解的概率为0.1%，我们执行100000次贪心，每次取最优，得到正解的概率是100% 也就是这种贪心也变成了某种意义上的正解
至于例子嘛.. 题目来源：http://www./problem/show?pid=1284 有N(3≤N≤40)块木板，每块的长度Li(1≤Li≤40)都是整数，利用所有的木板围成一个三角形使得面积最大。 计算出这个最大的面积。输入格式：第1行：一个整数N第2..N+1行：每行包含一个整数，即是木板长度。输出格式：仅一个整数：最大面积乘以100然后舍尾的结果。如果无法构建，输出-1。样例输入：511334样例输出：692 动态规划写法比较麻烦 我们考虑贪心，贪心原则不难想到，我们尽量让三边的差小，他的面积就大 所以每次将木板加入当前的最短边即可完成贪心 附上随机化贪心代码和测试详情 #include #include #include #include using namespace std;int n,a[41],ans=-1;void wash()//随机洗木板顺序{ for(int i=1;i<=n;i++) { int t=rand()%n; a[0]=a[t]; a[t]=a[i]; a[i]=a[0]; }}int hl(double aa,double bb,double cc)//海伦公式求面积{ if(aa+bb>cc&&bb+cc>aa&&aa+cc>bb) { double p=(aa+bb+cc)/2; return trunc(sqrt(p*(p-aa)*(p-bb)*(p-cc))*100); } else return -1;}void work()//贪心程序{ int p[3],pos; p[0]=a[1];p[1]=a[2];p[2]=a[3]; for(int i=4;i<=n;i++) { int min=0x7fffffff; for(int j=0;j<=2;j++) { if(min>p[j]) { min=p[j]; pos=j; } } p[pos]+=a[i]; } ans=max(ans,hl(p[0],p[1],p[2]));}int main(){ scanf('%d',&n); for(int i=1;i<=n;i++) scanf('%d',&a[i]); for(int i=1;i<=10000;i++) { wash(); work(); } printf('%d\n',ans); return 0;}
一共提交30遍(为了测试概率)，AC 30遍 测试点 #1：通过该测试点。 得分9，耗时0ms，内存2052kB。
测试点 #2：通过该测试点。 得分9，耗时0ms，内存2052kB。
测试点 #3：通过该测试点。 得分9，耗时0ms，内存2052kB。
测试点 #4：通过该测试点。 得分9，耗时0ms，内存2048kB。
测试点 #5：通过该测试点。 得分9，耗时15ms，内存2052kB。
测试点 #6：通过该测试点。 得分9，耗时15ms，内存2052kB。
测试点 #7：通过该测试点。 得分9，耗时15ms，内存2052kB。
测试点 #8：通过该测试点。 得分9，耗时15ms，内存2052kB。
测试点 #9：通过该测试点。 得分9，耗时15ms，内存2052kB。
测试点 #10：通过该测试点。 得分9，耗时15ms，内存2052kB。
测试点 #11：通过该测试点。 得分10，耗时31ms，内存2048kB。
实验证明，这是完美的骗分，足足骗了100分。。
|
