记忆的轮廓

题目描述

通往贤者之塔的路上，有许多的危机。
我们可以把这个地形看做是一颗树，根节点编号为1，目标节点编号为n，其中1-n的简单路径上，编号依次递增，在[1,n]中，一共有n个节点。我们把编号在[1,n]的叫做正确节点，[n+1,m]的叫做错误节点。一个叶子，如果是正确节点则为正确叶子，否则称为错误叶子。莎缇拉要帮助昴到达贤者之塔，因此现在面临着存档位置设定的问题。
为了让昴成长为英雄，因此一共只有p次存档的机会，其中1和n必须存档。被莎缇拉设置为要存档的节点称为存档位置。当然不能让昴陷入死循环，所以存档只能在正确节点上进行，而且同一个节点不能存多次档。因为通往贤者之塔的路上有影响的瘴气，因此莎缇拉假设昴每次位于树上一个节点时，都会等概率选择一个儿子走下去。每当走到一个错误叶子时，再走一步就会读档。具体的，每次昴到达一个新的存档位置，存档点便会更新为这个位置（假如现在的存档点是i，现在走到了一个存档位置j>i，那么存档点便会更新为j）。读档的意思就是回到当前存档点。初始昴位于1，当昴走到正确节点n时，便结束了路程。莎缇拉想知道，最优情况下，昴结束路程的期望步数是多少？

输入格式

第一行一个正整数T表示数据组数。
接下来每组数据，首先读入三个正整数n,m,p。
接下来m-n行，描述树上所有的非正确边（正确边即连接两个正确节点的边）
用两个正整数j，k表示j与k之间有一条连边，j和k可以均为错误节点，也可以一个为正确节点另一个为错误节点。
数据保证j是k的父亲。
50<=p<=n<=700，m<=1500，T<=5。
数据保证每个正确节点均有至少2个儿子，至多3个儿子。

输出格式

T行每行一个实数表示每组数据的答案。请保留四位小数。

样例

样例输入

1 3 7 2 1 4 2 5 3 6 3 7

样例输出

9.0000



题解

考场上推出了一个死掉的弱智算法
然而精度出了问题，加上本题根本没有小数据，被强行卡成了0分
我们不关注走到错误节点之后的去向
只要dfs处理出 每个正确节点的错误节点儿子走出树的期望步数即可
设dp（i，j）表示从第n个点，中间存了j个档，第j个存档在节点i的期望步数，
使用高斯消元的思想，我们可以得到dp（i，j）由dp（k，j-1）转移的公式 （i<k≤n）
dfs打出来即可
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;  5 const double inf=1e10;  6 const int N=720,M=1550;  7 int n,m,p,tot;  8 int first[M],to[M],nxt[M],cd[M];  9 double w[M],dp[N][N];  10 void dfs(int x)  11 {  12     if(x==n) return ;  13     if(x<n) dfs(x+1);  14     w[x]=1;  15     for(int i=first[x];i;i=nxt[i])  16  {  17  dfs(to[i]);  18         w[x]+=w[to[i]]/cd[x];  19  }  20 }  21 void add(int a,int b)  22 {  23     cd[a]++;  24     to[++tot]=b;  25     nxt[tot]=first[a];  26     first[a]=tot;  27 }  28 inline int read()  29 {  30     int x=0; char ch=getchar();  31     while(!isdigit(ch)) ch=getchar();  32     while(isdigit(ch))  33  {  34         x=(x<<1)+(x<<3)+(ch^48);  35         ch=getchar();  36  }  37     return x;  38 }  39 int th;  40 pair<double,double> search(int pos,int aim,int k)//系数 常数 
 41 {  42     pair<double,double> now,f;  43     if(pos>n)  44  {  45         now.first=1; now.second=w[pos];  46         return now;  47  }  48     if(pos==aim)  49  {  50         now.first=0; now.second=dp[aim][k]+1;  51         return now;  52  }  53     now.first=now.second=0;  54     f=search(pos+1,aim,k);  55     now.first+=f.first/cd[pos];  56     now.second+=f.second/cd[pos];  57     for(int i=first[pos];i;i=nxt[i])  58  {  59         f=search(to[i],aim,k);  60         now.first+=f.first/cd[pos];  61         now.second+=f.second/cd[pos];  62  }  63     if(pos!=th) now.second+=1;  64     return now;  65 }  66 void dpt(int pos,int k)//在pos处 第k个存档
 67 {  68     th=pos;  69     for(int i=pos+1;i<=min(n,n-k+2);i++)//由在i处 存k-1个档转移 
 70  {  71         pair<double,double> now=search(pos,i,k-1);  72         dp[pos][k]=min(dp[pos][k],now.second/(1-now.first));  73  }  74 }  75 int main()  76 {  77     int T; T=read();  78     while(T--)  79  {  80         memset(first,0,sizeof(first));  81         memset(cd,0,sizeof(cd));  82         tot=0;  83         n=read(); m=read(); p=read();  84         for(int i=0;i<=n;i++)  85             for(int j=0;j<=n;j++)  86                 dp[i][j]=inf;  87         for(int i=1,f,t;i<=m-n;i++)  88  {  89             f=read(); t=read();  90  add(f,t);  91  }  92         dfs(1);  93         for(int i=1;i<=m;i++) w[i]+=1;  94         for(int i=1;i<=n;i++) cd[i]++;  95         dp[n][1]=0;  96         for(int i=n-1;i>=1;i--)  97             for(int j=2;j<=min(p,n-i+1);j++)  98  dpt(i,j);  99         printf("%.4lf",dp[1][p]); 100  } 101     return 0; 102 } 103 /*
104 1 105 3 7 2 106 1 4 107 2 5 108 3 6 109 3 7 110 */
View Code

将重复的dfs删去，改成循环的形式，可以得到O（n2p）的算法

然而被卡了精度，只好改了longdouble

 

 

正解（或许）

四边形不等式：对于任意a<b<=c<d，

　　　　　　    转移代价w满足w(a,d)+w(b,c)<=w(a,c)+w(b,d)

对于形如    f[i]=max{f[i],f[j]+w(j,i)}    的转移方程

　　满足决策单调性，即如果i的最优决策点在j，大于i的任何元素的最优决策点一定大于等于j

预处理出从存档点i到存档点j的cost数组

结合实际意义发现满足四边形不等式

于是可以用决策单调性

使「1，n」区间决策「1，n」区间

在向下递归过程中，扫一遍决策区间，找出 被决策区间中点 的最优决策点

中点左侧的区间，由最优决策点及左侧的区间决策

右侧的区间由右侧的区间决策

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;  5 const int N=720,M=1550;  6 const double inf=1e99;  7 int n,m,p,tot,first[M],to[M],nxt[M],cd[M];  8 double w[M],dp[N][N],cost[N][N];  9 void dfs(int x) 10 { 11     if(x==n) return ; 12     if(x<n) dfs(x+1); 13     w[x]=1; 14     for(int i=first[x];i;i=nxt[i]) 15  { 16  dfs(to[i]); 17         w[x]+=w[to[i]]/cd[x]; 18  } 19 } 20 void add(int a,int b) 21 { 22     cd[a]++; 23     to[++tot]=b; 24     nxt[tot]=first[a]; 25     first[a]=tot; 26 } 27 inline int read() 28 { 29     int x=0; char ch=getchar(); 30     while(!isdigit(ch)) ch=getchar(); 31     while(isdigit(ch)) 32  { 33         x=(x<<1)+(x<<3)+(ch^48); 34         ch=getchar(); 35  } 36     return x; 37 } 38 void solve(int dep,int l,int r,int lf,int rf)//lf rf决策l到r
39 { 40     if(l>r) return ; 41     int mid=l+r>>1,home=lf; 42     dp[mid][dep]=inf; 43     for(int i=lf;i<=min(rf,mid-1);i++) 44  { 45         double tmp=dp[i][dep-1]+cost[i][mid]; 46         if(tmp<dp[mid][dep]) dp[mid][dep]=tmp,home=i; 47  } 48     solve(dep,l,mid-1,lf,home); 49     solve(dep,mid+1,r,home,rf); 50 } 51 int main() 52 { 53     int T; T=read(); 54     while(T--) 55  { 56         memset(first,0,sizeof(first)); 57         memset(cd,0,sizeof(cd)); 58         tot=0; 59         n=read(); m=read(); p=read(); 60         for(int i=1,f,t;i<=m-n;i++) 61  { 62             f=read(); t=read(); 63  add(f,t); 64  } 65         dfs(1); 66         for(int i=1;i<=m;i++) w[i]+=1; 67         for(int i=1;i<=n;i++) cd[i]++; 68         for(int i=1;i<=n;i++) 69  { 70             cost[i][i]=0; 71             for(int j=i+1;j<=n;j++) 72  { 73                 cost[i][j]=cd[j-1]*cost[i][j-1]+1; 74                 for(int u=first[j-1];u;u=nxt[u]) 75                     cost[i][j]+=w[to[u]]; 76  } 77  } 78         for(int i=1;i<=n;i++) dp[i][1]=inf; 79         dp[1][1]=0; 80         for(int i=2;i<=p;i++) 81             solve(i,1,n,1,n); 82         printf("%.4lf\n",dp[n][p]); 83  } 84     return 0; 85 }
View Code

刚开始做的时候inf设的不够大，导致无法更新，也就无法固定决策的区间，出现了问题