讨论 / PID234 LRJ的游戏只有60分
drcool 2013-12-31 18:27:50
点我顶贴 收藏 删除
我的程序只有60分,超时两个点,错误两个点。我的思路是深搜,到结束的时候计算轮数和概论的乘积,并累加结果,由于要求策略最优,那大家都应该打p[i]最小的人,这样才能尽快结束游戏。但是我看前面的讨论和程序并没有体现这一点,难度我的想法不对吗?

AC的同志们指教一下。

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

double p[6];

int de[6];

int xu[6];

int n;

double ans;

int stop;

int compare( const void *arg1, const void *arg2 )

{

int *A=arg1,*B=arg2;

if (p[*A]>p[*B]) return 1;

else if(p[*A]<p[*B]) return -1;

else return 0;

}

void dfs(int from,int deep, double p0,int nodead)

{

int i,j;

if(p0<1e-10) return;

if(nodead==1)

{

ans+=deep*p0;

return;

}

for(i=1;i<n;i++)

{

if(!de[(from+i)%n])

break;

}

dfs((from+i)%n,deep+1,p0*(1.0-p[from]),nodead);

for(j=0;j<n;j++)

if(!de[xu[j]]&&(xu[j]!=from))

break;

de[xu[j]]=1;

for(i=1;i<n;i++)

{

if(!de[(from+i)%n])

break;

}

dfs((from+i)%n,deep+1,p0*p[from],nodead-1);

de[xu[j]]=0;

}

int main()

{

int i,a;

scanf("%d",&n);

for(i=0;i<n;i++)

{

scanf("%d",&a);

p[i]=(double)a/100.0;

xu[i]=i;

}

qsort(xu,n,sizeof(int),compare);

dfs(0,0,1,n);

printf("%.3f",ans);

}

#1 drcool@2013-12-31 20:34:25
回复 删除
看来我的方法不对,应该是枚举打每一个人,取最小的结果才是最优的,另外还要使用极限的思想
查看更多回复
提交回复