【NOIP2016】換教室

題目戳我

題解

其實感覺16年的難度不是很大？？？？

這道題去年考場上DP都想出來了。。。

隻是因為不會數學期望。。。然後GG。。。。

這道題目隻要把數學期望搞出來就可以啦

設f[i][j][0/1]表示前i門課程中，已經換了j門，上一個課程是否換了教室

然後轉一下期望就可以啦。。。。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
using namespace std;
#define MAX 2010
#define INF 1000000000
int c[MAX],d[MAX];
double K[MAX];
int g[][];
double f[MAX][MAX][];
double s[MAX][MAX][];
int n,m,v,E;
int main()
{
    scanf("%d%d%d%d",&n,&m,&v,&E);
    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",&K[i]);
    for(int i=;i<=v;++i)
        for(int j=;j<=v;++j)
            if(i!=j)g[i][j]=INF;
    for(int i=;i<=E;++i)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        g[u][v]=g[v][u]=min(g[u][v],w);
    }
    for(int k=;k<=v;++k)
        for(int i=;i<=v;++i)
            for(int j=;j<=v;++j)
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
    //f[i][j][0/1]表示前i個課程中，申請j個，目前是否申請的期望
    for(int i=;i<=n;++i)
        for(int j=;j<=m;++j)
            f[i][j][]=f[i][j][]=INF;
    f[][][]=f[][][]=;
    for(int i=;i<=n;++i)
    {
        f[i][][]=f[i-][][]+g[c[i-]][c[i]]*;
        for(int j=;j<=m;++j)
        {
            f[i][j][]=f[i-][j][]+*g[c[i-]][c[i]];
            f[i][j][]=min(f[i][j][],f[i-][j][]+*K[i-]*g[d[i-]][c[i]]+*(-K[i-])*g[c[i-]][c[i]]);
            double t2;
            f[i][j][]=f[i-][j-][]+*K[i]*g[c[i-]][d[i]]+*(-K[i])*g[c[i-]][c[i]];
            t2=f[i-][j-][];
            t2+=K[i]*(*K[i-]*g[d[i-]][d[i]]+*(-K[i-])*g[c[i-]][d[i]]);
            t2+=(-K[i])*(*K[i-]*g[d[i-]][c[i]]+*(-K[i-])*g[c[i-]][c[i]]);            
            f[i][j][]=min(f[i][j][],t2);
        }
    }
    double ans=f[n][][];
    for(int i=;i<=m;++i)ans=min(f[n][i][],ans),ans=min(f[n][i][],ans);
    printf("%.2lf\n",ans);
    return ;    
}