洛谷1850(NOIp2016) 换教室——期望dp

题目：https://www.luogu.org/problemnew/show/P1850

状态里记录的是”上一回有没有申请“，而不是”上一回申请成功否“，不然“申请 j 次”就没法转移了。

double不能memset，所以手动。

别忘了dis[ i ][ i ]=0。

有重边！！！所以读入边的时候取一下min！

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define db double

using namespace std;

const int N=,V=,M=;

const db INF=0x3f3f3f3f;

int n,K,num,ent,c[N],d[N],dis[V][V];

db p[N],dp[][N][],ans=INF;

void mmst(db a[N][])

{

    for(int j=;j<=K;j++)a[j][]=a[j][]=INF;

}

int main()

{

    scanf("%d%d%d%d",&n,&K,&num,&ent);

    int x,y,z;

    for(int i=;i<=n;i++)scanf("%d",&c[i]);

    for(int i=;i<=n;i++)scanf("%d",&d[i]);

    for(int i=;i<=n;i++)scanf("%lf",&p[i]);

    memset(dis,0x3f,sizeof dis);

    while(ent--)

    {

        scanf("%d%d%d",&x,&y,&z);

        dis[x][y]=min(dis[x][y],z);dis[y][x]=dis[x][y];//?!////////

//        dis[x][y]=dis[y][x]=z;

    }

    for(int i=;i<=num;i++)dis[i][i]=;//

    for(int k=;k<=num;k++)

        for(int i=;i<=num;i++)

            for(int j=;j<=num;j++)

                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

    mmst(dp[]);

    dp[][][]=dp[][][]=;

    for(int i=;i<=n;i++)

    {

        int x=c[i-],y=c[i],u=d[i-],v=d[i],fx=(i&);

        mmst(dp[fx]);

        for(int j=;j<=K;j++)

        {

            dp[fx][j][]=min(dp[!fx][j][]+dis[x][y]

                ,dp[!fx][j][]+p[i-]*dis[u][y]+(-p[i-])*dis[x][y]);

            if(j)dp[fx][j][]=min(dp[!fx][j-][]+p[i]*dis[x][v]+(-p[i])*dis[x][y]

                ,dp[!fx][j-][]+p[i]*p[i-]*dis[u][v]+p[i]*(-p[i-])*dis[x][v]

                            +(-p[i])*p[i-]*dis[u][y]+(-p[i])*(-p[i-])*dis[x][y]);

        }

    }

    int fx=(n&);

    for(int j=;j<=K;j++)ans=min(ans,min(dp[fx][j][],dp[fx][j][]));

    printf("%.2lf\n",ans);

    return ;

}