首页 > 代码库 > UVALive 6514:Crusher’s Code(概率dp)
UVALive 6514:Crusher’s Code(概率dp)
题目链接 https://icpcarchive.ecs.baylor.edu/external/65/6514.pdf
题意：给出n个数（n<8） 求这n个数分别两个程序排成有序时，程序的期望迭代次数。排序程序如下。
// Monty‘s Codewhile (!sorted(a)) { int i = random(n) ; int j = random(n) ; if (a[min(i,j)] > a[max(i,j)]) swap(a[i], a[j]) ;}//Carlos‘s Codewhile (!sorted(a)) { int i = random(n-1) ; int j = i + 1 ; if (a[i] > a[j]) swap(a[i], a[j]) ;}
思路：正常的概率dp。这里“亮”的地方在与，其状态的定义就暴力的定义成了这个串。……因为 8! < 50000。 所以能过。
代码[略锉]:
#include <algorithm>#include <cstdio>#include <cstring>#include <map>using namespace std;map<int,int> id;int idp;int isSortedA;double e[50000];int getid(int a) { if (id[a] == 0) id[a] = idp++; return id[a];}int hash(int a[], int n) { int ret = 0; for (int i = 0; i < n; i++) { ret = ret*10 + a[i]; } return ret;}int n;//monty(anow) = p1*monty(anext1) + p2*monty(anext2) + .. + (1-p1-p2)*monty(anow) + 1;//p = 2/n*ndouble monty(int a) { if (a == isSortedA) return 0; if (e[getid(a)] != 0) return e[getid(a)]; int tmp[10]; int tmpa = a; for (int i = n-1; i >= 0; i-- ) { tmp[i] = tmpa%10; tmpa/=10; } int num = 0; for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { if (tmp[i] > tmp[j]) num++; } } if (num == 0) { isSortedA = a; return 0; } double ans = n*n/(num*2.0); for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { if (tmp[i] > tmp[j]) { swap(tmp[i], tmp[j]); ans += 1.0/num * monty(hash(tmp,n));; swap(tmp[i], tmp[j]); } } } return e[getid(a)] = ans;}double carlos(int a) { if (a == isSortedA) return 0; if (e[getid(a)] != 0) return e[getid(a)]; int tmp[10]; int tmpa = a; for (int i = n-1; i >= 0; i-- ) { tmp[i] = tmpa%10; tmpa/=10; } int num = 0; for (int i = 0; i < n-1; i++) { if (tmp[i] > tmp[i+1]) num++; } if (num == 0) { isSortedA = a; return 0; } double ans = (n-1.0)/num; for (int i = 0; i < n-1; i++) { int j = i+1; if (tmp[i] > tmp[j]) { swap(tmp[i], tmp[j]); ans += 1.0/num * carlos(hash(tmp,n));; swap(tmp[i], tmp[j]); } } return e[getid(a)] = ans;}int a[10];int main() { int t; scanf("%d", &t); while (t--) { isSortedA = -1; scanf("%d", &n); int tmp[10]; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); tmp[i] = a[i]; } sort(tmp, tmp+n); unique(tmp, tmp+n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (a[i] == tmp[j]) { a[i] = j; break; } } } idp = 0; id.clear(); memset(e,0,sizeof(e)); printf("Monty %.6lf ", monty(hash(a,n))); idp = 0; id.clear(); memset(e,0,sizeof(e)); printf("Carlos %.6lf\n", carlos(hash(a,n)));; } return 0;}
UVALive 6514:Crusher’s Code(概率dp)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。