「BZOJ4899」 记忆的轮廓
题意：从根节点 \(1\) 走到 \(n\)，会等概率选择一个儿子走下去，其中 \(1-n\) 的简单路径上编号依次递增，编号在 \([1,n]\) 的叫做正确节点，\([n+1,m]\) 的叫做错误节点，一共有 \(p\) 次存档的机会，\(1\) 和 \(n\) 必须存档，存档只能在正确节点上进行，而且同一个节点不能存多次档，每次到达一个新的正确节点，便可以在这里设立存档点，每当走到一个错误叶子时，就回到当前存档点，最优情况下，期望步数是多少
考虑一个特殊的点 \(p=n\)，因为最优，所以一定每个节点都会设立，记 \(d_i\) 为 \(i\) 的儿子节点数量，\(dp3_i\) 表示期望走多少步就会回到存档点 \((n+1\le i \le m)\)，\(f_i\) 表示走期望多少步能到达终点 \((1 \le i \le n)\)
那么 \(dp3_i=\frac{\sum dp3_j}{d_i}+1\)（注意特判 \(d_i=0\) 的情况，\(j\) 为 \(i\) 的儿子节点）
\(f_i=\frac{f_{i+1}}{d_i}+\frac{\sum (dp3_j+f_i)}{d_i}+1\)，注意因为走错了要回到 \(i\) 重新走，所以是 \(\sum (dp3_j+f_i)\)，化简得 \(f_i=f_{i+1}+d_i+\sum dp3_j\) （\(j\) 为 \(i\) 的错误儿子节点）
时间复杂度 \(O(n)\)，得分 \(50pts\)，注意下面代码把 \(f_i\) 和 \(dp3_i\) 合并写成了 \(dp_i\)
#include<bits/stdc++.h>
using namespace std;
int t,n,m,p,x,y;
double dp[1501];
vector <int> G[1501];
double get(int x){
if(dp[x]) return dp[x];
for(int i=0;i<G[x].size();i++){
get(G[x][i]);
dp[x]+=dp[G[x][i]];
}
if(!G[x].size()) dp[x]=1;
else dp[x]=1.0*dp[x]/G[x].size()+1;
return dp[x];
}
int main(){
scanf("%d",&t);
while(t--){
memset(dp,0,sizeof(dp));
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=m;i++) G[i].clear();
for(int i=1;i<=m-n;i++){
scanf("%d%d",&x,&y);
G[x].push_back(y);
}
for(int i=n-1;i>=1;i--){
for(int j=0;j<G[i].size();j++) dp[i]+=get(G[i][j]);
dp[i]+=1.0*G[i].size()+dp[i+1]+1;
}
printf("%.4lf\n",dp[1]);
}
return 0;
}
考虑普通情况，由于我们不知道存档点在哪儿，所以我们只能枚举当前要在哪儿设置与上一次在哪儿设置的，那么记 \(dp1_{i,j}\) 表示从 \(1\) 到 \(j\) 的期望步数，且存了 \(i\) 次档，但我们发现，中间的那些点的贡献又需要枚举来计算，但是时间复杂度无法承受，那么只能预处理出来，记 \(dp2_{i,j}\) 表示只在 \(i\) 设立了存档点，从 \(i\) 到 \(j\) 的期望步数
易得 \(dp1_{i,j}=min(dp1_{i-1,k}+dp2_{k,j})\)
\(dp2_{i,j}=dp2_{i,j-1}+\frac{\sum(dp3_{l}+dp2_{i,j})}{d_{j-1}}+1\)，理由和上面的差不多，化简得 \(dp2_{i,j}=d_{j-1} \times dp2_{i,j-1}+\sum dp3_{l}+d_{j-1}\)（\(l\) 为 \(j-1\) 的错误儿子节点）
时间复杂度 \(O(n^2p)\)，得分 \(80pts\)（换语言能过）
#include<bits/stdc++.h>
using namespace std;
int t,n,m,p,x,y;
double dp1[701][701],dp2[701][701],dp3[1501];
vector <int> G[1501];
double get(int x){
if(dp3[x]) return dp3[x];
for(int i=0;i<G[x].size();i++){
get(G[x][i]);
dp3[x]+=dp3[G[x][i]];
}
if(!G[x].size()) dp3[x]=1;
else dp3[x]=1.0*dp3[x]/G[x].size()+1;
return dp3[x];
}
int main(){
scanf("%d",&t);
while(t--){
memset(dp1,127,sizeof(dp1));
memset(dp2,0,sizeof(dp2));
memset(dp3,0,sizeof(dp3));
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=m;i++) G[i].clear();
for(int i=1;i<=m-n;i++){
scanf("%d%d",&x,&y);
G[x].push_back(y);
}
for(int i=1;i<=n;i++){
dp2[i][i]=0;
for(int j=i+1;j<=n;j++){
for(int l=0;l<G[j-1].size();l++) dp2[i][j]+=get(G[j-1][l]);
dp2[i][j]+=1.0*(dp2[i][j-1]+1)*(G[j-1].size()+1);
}
}
dp1[1][1]=0;
for(int i=2;i<=p;i++){
for(int j=2;j<=n;j++){
for(int k=1;k<j;k++) dp1[i][j]=min(dp1[i][j],dp1[i-1][k]+dp2[k][j]);
}
}
printf("%.4lf\n",dp1[p][n]);
}
return 0;
}
发现瓶颈在 \(dp1_{i,j}\) 上，发现它很像基于分治的决策单调性优化形式，打表发现的确满足决策单调性，感性理解 \(dp2_{i,j}\) 单调递增，且增加得越来越快，只能选到恰好合适，也可以二分等方法优化
时间复杂度 \(O(pn\) \(log\) \(n)\)，得分 \(100pts\)
#include<bits/stdc++.h>
using namespace std;
int t,n,m,p,x,y;
double dp1[701][701],dp2[701][701],dp3[1501];
vector <int> G[1501];
double get(int x){
if(dp3[x]) return dp3[x];
for(int i=0;i<G[x].size();i++){
get(G[x][i]);
dp3[x]+=dp3[G[x][i]];
}
if(!G[x].size()) dp3[x]=1;
else dp3[x]=1.0*dp3[x]/G[x].size()+1;
return dp3[x];
}
void solve(int tim,int L,int R,int ql,int qr){
if(L>R) return;
int mid=(L+R)>>1,now=0;
for(int i=ql;i<=min(mid-1,qr);i++){
double val=dp1[tim-1][i]+dp2[i][mid];
if(val<dp1[tim][mid]) dp1[tim][mid]=val,now=i;
}
solve(tim,L,mid-1,ql,now);
solve(tim,mid+1,R,now,qr);
}
int main(){
scanf("%d",&t);
while(t--){
memset(dp1,127,sizeof(dp1));
memset(dp2,0,sizeof(dp2));
memset(dp3,0,sizeof(dp3));
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=m;i++) G[i].clear();
for(int i=1;i<=m-n;i++){
scanf("%d%d",&x,&y);
G[x].push_back(y);
}
for(int i=1;i<=n;i++){
dp2[i][i]=0;
for(int j=i+1;j<=n;j++){
for(int l=0;l<G[j-1].size();l++) dp2[i][j]+=get(G[j-1][l]);
dp2[i][j]+=1.0*(dp2[i][j-1]+1)*(G[j-1].size()+1);
}
}
dp1[1][1]=0;
for(int i=2;i<=p;i++) solve(i,1,n,1,n);
printf("%.4lf\n",dp1[p][n]);
}
return 0;
}