【BZOJ4899】记忆的轮廓-期望DP+决策单调性优化DP

做法：本题需要用到期望DP+决策单调性优化DP。
令}
其中j个点的期望步数。显然我们要先预处理出来这个东西才能DP。
首先考虑一个点能走到的所有错误节点，令)
这个式子的意义是，要走到)
于是我们就可以g了。
再回到求)。
先考虑左边，把)≥1，所以上面的不等式得证，于是这个方程满足决策单调性。
知道了这一点之后，直接用模板优化成)即可。
以下是本人代码：

#include <bits/stdc++.h>
using namespace std;
const double eps=1e-7;
int T,n,m,p,first[2010]={0},tot=0;
double deg[2010],f[2010][2010],g[2010][2010],step[2010]={0};
int q[2010],l[2010],r[2010];
struct edge
{
    int v,next;
}e[2010];

void insert(int a,int b)
{
    e[++tot].v=b;
    e[tot].next=first[a];
    first[a]=tot;
}

void dp(int v)
{
    deg[v]=step[v]=0.0;
    for(int i=first[v];i;i=e[i].next)
    {
        dp(e[i].v);
        deg[v]+=1.0;
        step[v]+=step[e[i].v];
    }
    if (deg[v]>0.5) step[v]/=deg[v];
    step[v]+=1.0;
}

double calc(int l,int r,int k)
{
    return f[l][k]+g[l][r];
}

int solve(int k,int l,int r,int i,int j)
{
    r++;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if (calc(k,mid,j-1)+eps>calc(i,mid,j-1))
            r=mid;
        else l=mid+1;
    }
    return l;
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&p);
        memset(first,0,sizeof(first));
        tot=0;
        for(int i=1;i<=m-n;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            insert(a,b);
        }

        for(int i=1;i<=n;i++)
        {
            deg[i]=step[i]=0.0;
            for(int j=first[i];j;j=e[j].next)
                if (e[j].v>n)
                {
                    deg[i]+=1.0;
                    dp(e[j].v);
                    step[i]+=step[e[j].v];
                }
            deg[i]+=1.0;
        }

        for(int i=1;i<=n;i++)
        {
            g[i][i]=0.0;
            for(int j=i+1;j<=n;j++)
                g[i][j]=deg[j-1]*g[i][j-1]+deg[j-1]+step[j-1];
        }

        for(int i=1;i<=n;i++)
            f[i][1]=g[1][i];
        for(int j=2;j<p;j++)
        {
            int h=1,t=1;
            q[h]=1,l[h]=1,r[h]=n;
            for(int i=1;i<=n;i++)
            {
                if (i==42)
                    t++,t--;
                f[i][j]=calc(q[h],i,j-1);
                l[h]++;
                if (h<=t&&r[h]<l[h]) h++;
                if (h>t||calc(q[t],n,j-1)+eps>calc(i,n,j-1))
                {
                    while(h<=t&&calc(q[t],l[t],j-1)+eps>calc(i,l[t],j-1)) t--;
                    if (h>t) q[++t]=i,l[t]=i+1,r[t]=n;
                    else
                    {
                        int tmp=solve(q[t],l[t],r[t],i,j);
                        r[t]=tmp-1;
                        q[++t]=i,l[t]=tmp,r[t]=n;
                    }
                }
            }
        }
        printf("%.4lf
",f[n][p-1]);
    }

    return 0;
}