【poj2057】The Lost House

Source and Judge

poj2057

Record

2h

Analysis

请先思考后再展开

感觉这个期望的柿子很不好推啊,我也是看了提示才想到的
提示:
将以x为根节点的子树代价,分答案是否在其中考虑,其期望分别为f和g


“贪婪的动态规划”论文上没有利用期望的线性性,而我感觉用的话容易理解一点……
我的方程:
$g(x)=\sum 2+有虫子则g(y)$
假如我们已经知道某个遍历顺序(尝试顺序,可能走到一半出来)
然后考虑枚举某个孩子,答案就在这里的贡献
$f(x)=\sum 该后继状态发生的可能 \times 该状态的期望$
$f(x)=\sum \frac{叶子数量}{总叶子数量} ( \sum( g(s_1 \to s_{i-1})+2 ) + f(y)+1 )$
注意这里g的计算规则和上面g那个一样,根据虫子跳出,具体实现可以前缀和

然后因为题目保证孩子数量最大为8,可以预处理所有排列,可通过本题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAX_N=1100;
int son[MAX_N][10];
struct Nod{int s[10];}now;
vector<Nod> pl[10];
bool use[10];
void dfs(int n,int k)
{
if(k==n+1) {pl[n].push_back(now);return;}
for(int i=1;i<=n;i++) if(!use[i]) use[i]=1,now.s[k]=i,dfs(n,k+1),use[i]=0;
}
double f[MAX_N],g[MAX_N];
bool cz[MAX_N];
int leave[MAX_N];
void solve(int x)
{
int snum=son[x][0];
if(snum==0) leave[x]=1;
else
{
for(int i=1;i<=son[x][0];i++)
{
int y=son[x][i];
solve(y);
g[x]+=(cz[y]?0:g[y])+2;
leave[x]+=leave[y];
}
for(int t=0;t<(int)pl[snum].size();t++)
{
double tmp=0,nowg=0;
for(int i=1;i<=snum;i++)
{
int y=son[x][ pl[snum][t].s[i] ];
tmp+=(nowg+f[y]+1)*leave[y];
nowg+=(cz[y]?0:g[y])+2;
}
f[x]=min(f[x],tmp/leave[x]);
}
//printf("f[%d]=%lf g[x]=%lf\n",x,f[x],g[x]);
}
}
void main()
{
for(int i=1;i<=8;i++) dfs(i,1);
while(1)
{
int n,rt;scanf("%d",&n);
if(n==0) break;
memset(son,0,sizeof son);
memset(leave,0,sizeof leave);
for(int i=1;i<=n;i++)
{
int fa;char str[4];scanf("%d%s",&fa,str);
cz[i]=(str[0]=='Y');
if(fa<0) rt=i;
else son[fa][++son[fa][0]]=i;
}
for(int i=1;i<=n;i++) g[i]=0,f[i]=(son[i][0]==0)?0:INF;
solve(rt);
printf("%.4lf\n",f[rt]);
}
}
};
int main()
{
mine::main();
}

其实还有更快的做法
考虑相邻的两个,他们产生的贡献,=推推柿子,再交换一下,就会变成:
g的贡献(g(x)+2,同样考虑虫子来计算),除以其叶子数量
那么这个比较只和自己有关,可以直接排序

这样1000个孩子我都不怕了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAX_N=1100;
int son[MAX_N][10];
double f[MAX_N];
int g[MAX_N];
bool cz[MAX_N];
int leave[MAX_N];
bool cmp(int a,int b) {return double(g[a]+2)*leave[b]<double(g[b]+2)*leave[a];}
void solve(int x)
{
int snum=son[x][0];
if(snum==0) leave[x]=1;
else
{
for(int i=1;i<=snum;i++)
{
int y=son[x][i];
solve(y);
leave[x]+=leave[y];
g[x]+=g[y]+2;
}
sort(son[x]+1,son[x]+snum+1,cmp);
double nowg=0;
for(int i=1;i<=snum;i++)
{
int y=son[x][i];
f[x]+=(nowg+f[y]+1)*leave[y];
nowg+=g[y]+2;
}
f[x]/=leave[x];
if(cz[x]) g[x]=0;
}
}
void main()
{
while(1)
{
int n,rt;scanf("%d",&n);
if(n==0) break;
memset(son,0,sizeof son);
memset(leave,0,sizeof leave);
memset(f,0,sizeof f);
memset(g,0,sizeof g);
for(int i=1;i<=n;i++)
{
int fa;char str[4];scanf("%d%s",&fa,str);
cz[i]=(str[0]=='Y');
if(fa<0) rt=i;
else son[fa][++son[fa][0]]=i;
}
solve(rt);
printf("%.4lf\n",f[rt]);
}
}
};
int main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/4075.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%