【题解】NOIP2016换教室

哇好开心啊！写的时候真的全然对于这个加法没有把握，但还是大着胆子试着写了一下——竟然过了样例？于是又调了一下就过啦。

不过想想也觉得是正确的吧，互相独立的事件对于期望的影响自然也是相互独立的，可以把所有的情况看成一个整体，不同的统计方式只是分组的区别，最后算出来的答案肯定是一样的。dp的状态比较显然：dp[i][j][0/1]代表当前在第i节课，已经用去了j次申请的机会，0/1分别代表当前这一节课是否申请。那么这个时候就分情况讨论，计算这一次的选择对于答案的影响。

这些不同的情况分别是：当前和上一次是否选择申请换课，申请换课的是否成功。

期望的计算式：成功的概率*成功的代价+失败的概率*失败的代价。

#include <bits/stdc++.h>

using namespace std;

#define maxn 2050

#define INF 1047483640

#define maxm 2050

#define maxv 400

int n, m, v, e, dis[maxv][maxv], c[maxn], d[maxn];

double ans = , dp[maxn][maxm][], k[maxn];

int read()

{

    int x = , k = ;

    char c;

    c = getchar();

    while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * k;

}

void init()

{

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

        for(int j = i + ; j <= v; j ++)

            dis[i][j] = dis[j][i] = INF;

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

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

            dp[i][j][] = dp[i][j][] = INF;

}

double gmin(double &x, double y)

{

    x = (x < y) ? x : y;

}

int gmin2(int &x, int y)

{

    x = (x < y) ? x : y;

}

void Floyd()

{

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

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

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

                gmin2(dis[i][j], dis[i][k] + dis[k][j]);

}

int main()

{

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

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

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

    init();

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

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

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

    {

        int x = read(), y = read(), z = read();

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

    }

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

    Floyd();

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

        dis[i][] = dis[][i] = ;

    c[] = d[] = , k[] = ;

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

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

        {

            gmin(dp[i][j][], dp[i - ][j][] + dis[c[i]][c[i - ]]);

            gmin(dp[i][j][], dp[i - ][j][] + dis[c[i]][c[i - ]] * ( - k[i - ]) + dis[c[i]][d[i - ]] * k[i - ]);

            if(j) gmin(dp[i][j][], dp[i - ][j - ][] + dis[c[i]][c[i - ]] * ( - k[i]) + dis[d[i]][c[i - ]] * k[i]);

            double tem = ;

            tem += dis[c[i]][c[i - ]] * ( - k[i]) * ( - k[i - ]);

            tem += dis[c[i]][d[i - ]] * ( - k[i]) * k[i - ];

            tem += dis[d[i]][c[i - ]] * k[i] * ( - k[i - ]);

            tem += dis[d[i]][d[i - ]] * k[i] * k[i - ];

            if(j) gmin(dp[i][j][], dp[i - ][j - ][] + tem);

        }

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

        gmin(ans, min(dp[n][i][], dp[n][i][]));

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

    return ;

}

巴特西

【题解】NOIP2016换教室

最新文章

热门文章