[noip2016]换教室

发表于 2017-10-31   |   分类于 未分类

期望dp,由于当时不知道啥是数学期望,题目看了十遍,打了暴力,还打爆了,,,,

这个dp可以说是相当简单粗暴了,,【公式极长,一行写不下

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int _maxn=2010;
int n,m,v,e,b[_maxn],a[_maxn];
double k[_maxn],f[_maxn][_maxn][2],inf=999999999,g[_maxn][_maxn];
double mindou(double x,double y){
    if(x>y)    return y;
    return x;
}
int main(){
//    freopen("test.in","r",stdin);
    scanf("%d%d%d%d",&n,&m,&v,&e);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)
        scanf("%lf",&k[i]);
    for(int i=0;i<=v;i++){
        for(int j=0;j<=v;j++)
            g[i][j]=inf;
        g[i][i]=0;
        g[0][i]=0;
    }
    int x,y,z;
    for(int i=1;i<=e;i++){
        scanf("%d%d%d",&x,&y,&z);
        g[x][y]=g[y][x]=mindou(g[x][y],(double)z);
    }
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int l=0;l<2;l++)
                f[i][j][l]=inf;
    for(int i=1;i<=v;i++)
        for(int j=1;j<=v;j++)
            for(int l=1;l<=v;l++)
                if(g[j][i]+g[i][l]<g[j][l])
                    g[j][l]=g[j][i]+g[i][l];
    f[0][0][0]=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<=m;j++){
            f[i+1][j][0]=mindou(f[i][j][0]+g[a[i]][a[i+1]],f[i][j][1]+k[i]*g[b[i]][a[i+1]]+(1-k[i])*g[a[i]][a[i+1]]);
            if(j!=m){
                f[i+1][j+1][1]=mindou(f[i][j][0]+g[a[i]][a[i+1]]*(1-k[i+1])+g[a[i]][b[i+1]]*k[i+1],
                f[i][j][1]+g[a[i]][a[i+1]]*(1-k[i])*(1-k[i+1])+g[a[i]][b[i+1]]*(1-k[i])*k[i+1]+g[b[i]][a[i+1]]*k[i]*(1-k[i+1])+g[b[i]][b[i+1]]*k[i]*k[i+1]); 
            }
        }
    }
    double ans=inf;
    for(int i=0;i<=m;i++)
        for(int l=0;l<2;l++)
            ans=mindou(ans,f[n][i][l]);
    printf("%.2lf\n",ans);
    return 0;
}

发表新评论

© 2017 Powered by Typecho & Theme Quark