【NOIP16提高组】换教室

【题目链接】

【算法】

概率DP

先跑一遍floyed，求出每个教室之间的最短路径，存在数组dist[][]中，时间复杂度O(V^3)

设计状态，f[i][j][k]表示当前选到第i个教室，已经选了j个教室，当前这个教室选不选（0..1)

那么，状态转移方程是什么呢？

假设当前选到第i个教室，已经选了j个教室，那么，如果不选这个教室，则状态转移方程为

f[i][j][0] = max{f[i-1][j][0]+dist[c[i-1]][c[i]],f[i-1][j][1]+dist[c[i-1]][c[i]]*(1-k[i-1])+dist[d[i-1]][c[i]]*k[i-1]}

如果选这个教室，则状态转移方程是

f[i][j][1] = min{f[i-1][j-1][0]+dist[c[i-1]][d[i]]*k[i]+dist[c[i-1]][c[i]]*(1-k[i],f[i-1][j-1][1]+dist[d[i-1]][d[i]]*k[i-1]*k[i]+dist[c[i-1]][d[i]]*(1-k[i-1])*k[i]+dist[c[i-1]][c[i]]*(1-k[i-1])*(1-k[i])+dist[d[i-1]][c[i]]*k[i-1]*(1-k[i])}

于是这道题便迎刃而解了！

【代码】

#include<bits/stdc++.h>

using namespace std;

#define MAXN 2000

#define MAXV 300

int i,j,k,n,m,v,e,a,b,w;

int dist[MAXV+][MAXV+],c[MAXN+],d[MAXN+];

double P[MAXN+],dp[MAXN+][MAXN+][];

double ans = 2e9;

template <typename T> inline void read(T &x) {

        int f=; x=;

        char c = getchar();

        for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; }

        for (; isdigit(c); c = getchar()) x = x *  + c - '';

        x *= f;

}

template <typename T> inline void write(T x) {

    if (x < ) { putchar('-'); x = -x; }

    if (x > ) write(x/);

    putchar(x%+'');

}

template <typename T> inline void writeln(T x) {

    write(x);

    puts("");

}

int main() {

        read(n); read(m); read(v); read(e);

        for (i = ; i <= v; i++) {

                for (j = ; j <= v; j++) {

                        if (i != j)

                                dist[i][j] = 2e9;

                }

        }

         for (i = ; i <= n; i++) read(c[i]);

        for (i = ; i <= n; i++) read(d[i]);

        for (i = ; i <= n; i++) cin >> P[i];

        for (i = ; i <= e; i++) {

                read(a); read(b); read(w);

                dist[a][b] = min(dist[a][b],w);

                dist[b][a] = min(dist[b][a],w);

        }

        for (k = ; k <= v; k++) {

                for (i = ; i <= v; i++) {

                        if (i == k) continue;

                        if (dist[i][k] == 2e9) continue;

                        for (j = ; j <= v; j++) {

                                if (dist[k][j] == 2e9) continue;

                                if ((i == j) || (k == j)) continue;

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

                        }

                }

        }    

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

                for (j = ; j <= m; j++) {

                        dp[i][j][] = dp[i][j][] = 2e9;

                }

        }

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

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

                dp[i][][] = dp[i-][][] + dist[c[i-]][c[i]];

                for (j = ; j <= min(i,m); j++) {

                        dp[i][j][] = min(dp[i-][j][]+dist[c[i-]][c[i]],dp[i-][j][]+dist[c[i-]][c[i]]*(1.0-P[i-])+dist[d[i-]][c[i]]*P[i-]);

                        dp[i][j][] = min(dp[i-][j-][]+dist[c[i-]][d[i]]*P[i]*1.0+dist[c[i-]][c[i]]*(1.0-P[i]),

                                                            dp[i-][j-][]+

                                                            dist[d[i-]][d[i]]*P[i-]*P[i]*1.0+

                                                            dist[c[i-]][d[i]]*(1.0-P[i-])*P[i]+

                                                            dist[c[i-]][c[i]]*(1.0-P[i-])*(1.0-P[i])+

                                                                dist[d[i-]][c[i]]*P[i-]*(-P[i])*1.0);

                }

        }

        for (i = ; i <= m; i++) ans = min(ans,min(dp[n][i][],dp[n][i][]));

        cout<< fixed << setprecision() << ans << endl;

        return ;

}

巴特西

【NOIP16提高组】换教室

最新文章

热门文章