"记忆的轮廓"

"记忆的轮廓"
很好的一道期望题,暑假时学长讲的,不过当时用的是 WerKeyTom_FTD 给的第二种解法,现在用的是 skyh 学长的决策单调性(分治写法)

首先不难得到期望转移式

我们令 \(a_{i,j}\) 表示存档点在 \(i\) 点 走到 \(j\) 点的期望步数

\(g_{i}\) 表示从该错误节点走到存档点的期望步数

则:

\[a_{i,j+1}=a_{i,j}+\dfrac{1}{du_j}+\left( \dfrac{du_j-1}{du_j}+\dfrac{1}{du_j}\sum_{k\epsilon son(j)}g(k) \right) \]

\[a_{i,J+1}=du_j*a_{i,j}+1+S(j) \]

其中 \(S(i)=\sum_{k\epsilon son(i)}g(k)\)

接着我们会得到一个类似背包的一个东西:
令 \(f_{i,j}\) 表示在 \(i\) 点存档 共存档 \(j\) 次的最小到达期望步数

则 \(f_{i,j}=min\{ f_{k,j-1}+a_{k,i} \}\)

这样转移是 \(n^3\) 的,我们不妨来观察一下该 \(a\) 式子

\[a_{i,j+1}-a_{i,j} \]

\[(du_j-1)*a_{i,j}+du_j+S(j) \]

\[a_{i+1,j+1}-a_{i+1,j} \]

\[(du_j-1)*a_{i+1,j}+du_j+S(j) \]

显然有 \(a_{i,j}>=a_{i+1,j}\)

所以:

\[a_{i,j+1}-a_{i,j}>=a_{i+1,j+1}-a_{i+1,j} \]

\[a_{i,j+1}-a_{i+1,j+1}>=a_{i,j}-a_{i+1,j} \]

也就是说对于任意 \(l>j\),\(a_{x,l}\) 的增量大于 \(a_{x,j}\) 的增量

形式化的,我们令函数 \(S(j)=f_{x,p-1}+a_{x,j},S(l)=f_{x,p-1}+a_{x,l}\)

那么两个函数有且仅有一个交点,所以我们其实就是要维护一个类似下凸包的东西

其实也就是对于 \(l\) 点和 \(j\) 点 \((l>j)\) ,\(l\) 的最优决策点一定大于等于 \(j\) 的最优决策点

我们可以用分治来解决此问题

Code
/* memory */
#include <bits/stdc++.h>
#define re register
// #define int long long
#define lls long long
#define fr first
#define sc second
#define pb push_back
#define db double
using namespace std;
const int maxn=1e5+10;
const int mol=998244353;
const db INF=1e99;
inline int read() {
    int w=1,s=0; char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { s=s*10+ch-'0'; ch=getchar(); }
    return s*w;
}

int n,m,t,p,du[2020];
struct EDGE { int var,nxt; } edge[maxn<<1];
int head[maxn],cnt;
inline void add(int a,int b) { edge[++cnt]=(EDGE){ b,head[a] }; head[a]=cnt; }
db g[2020],a[2020][2020],f[2020][2020];
inline void clear() {
    for(re int i=1;i<=m;i++) head[i]=-1,g[i]=0,du[i]=0; cnt=0;
}
inline db dfs(int now,int fa) {
    bool o=0; db as=0;
    for(re int i=head[now],to;~i;i=edge[i].nxt) if((to=edge[i].var)!=fa) {
        as+=(dfs(to,now)+1.0)/(db)(du[now]-1.0); o=1;
    }
    if(!o) return 1.0; return as; 
}
inline void wor(int p,int l,int r,int ll,int rr) {
    if(l>r) return ;
    int fg=ll,mid=(l+r)>>1; db tmp;
    f[mid][p]=INF; 
    for(re int i=ll,lim=min(mid-1,rr);i<=lim;i++) {
        tmp=f[i][p-1]+a[i][mid];
        if(tmp<f[mid][p]) { f[mid][p]=tmp; fg=i; }
    }
    wor(p,l,mid-1,ll,fg); wor(p,mid+1,r,fg,rr); 
}
inline void slove() {
    n=read(); m=read(); p=read(); clear();
    for(re int i=1,a,b;i<=m-n;i++) { a=read(); b=read(); add(a,b); add(b,a); du[a]++; du[b]++; }
    for(re int now=1;now<=n;now++) { for(re int i=head[now];~i;i=edge[i].nxt) g[now]+=dfs(edge[i].var,now); }
    for(re int i=1;i<=n;i++) for(re int j=i+1;j<=n;j++) a[i][j]=a[i][j-1]*(db)(du[j-1]+1.0)+(db)(du[j-1]+1.0)+g[j-1];
    f[1][1]=0; for(re int i=2;i<=n;i++) f[i][1]=INF;
    for(re int i=2;i<=p;i++) wor(i,1,n,1,n); 
    printf("%.4lf\n",f[n][p]);
}
signed main(void) {
    t=read(); while(t--) { slove(); }
}

上一篇:BZOJ_1954_Pku3764 The xor-longest Path_Trie树


下一篇:Linux系统查看磁盘可用空间的5个命令