【题解】[NOIP2017]换教室 NOIP瞎搞系列

请注意,本文编写于 250 天前,最后修改于 248 天前,其中某些信息可能已经过时。

传送门 >ω< UOJ
传送门 >ω< Luogu

比较简单的一个 DP ,可能是因为这是 NOIP 第一次引进期望所以特别裸?

Solution

观察发现每一节课留在原地或换教室所提高的期望仅仅和上一节课的教室有关
那么就很简单了

  • $f[i][j][0]$ 表示前 $i$ 节课换了 $j$ 次,其中最后一次没换的最小期望
  • $f[i][j][1]$ 表示前 $i$ 节课换了 $j$ 次,其中最后一次换了的最小期望

再考虑下上次是否换成功,这次是否换成功
即可得到转移:

$f[i][j][0] =$
上次不换: $f[i - 1][j][1] * dis[c[i]][c[i]]$
上次换,成功: $k[i - 1] * f[i - 1][j][1] * dis[d[i - 1]][c[i]]$
上次换,失败: $(1.0 - k[i - 1]) * f[i - 1][j][1] * dis[c[i - 1]][c[i]]$

$f[i][j][1] =$
上次不换,这次成功: $k[i] * (f[i - 1][j][0] + dis[c[i - 1]][d[i]])$
上次不换,这次失败: $(1 - k[i]) * (f[i - 1][j][0] + dis[c[i - 1]][c[i]])$
上次换,成功,这次成功: $k[i - 1] * k[i] * (f[i - 1][j - 1][1] + dis[d[i - 1]][d[i]])$
上次换,成功,这次失败: $k[i - 1] * (1 - k[i]) * (f[i - 1][j - 1][1] + dis[d[i - 1]][c[i]])$
上次换,失败,这次成功: $(1.0 - k[i - 1]) * k[i] * (f[i - 1][j - 1][1] + dis[c[i - 1]][d[i]])$
上次换,失败,这次失败: $(1.0 - k[i - 1]) * (1.0 - k[i]) * (f[i - 1][j - 1][1] + dis[c[i - 1]][c[i]])$

有点复杂,但是很清晰
就这样愉快的 A 掉了!

代码

#include <bits/stdc++.h>
using namespace std;
const double INF = 0x3f3f3f3f;
const int N = 2100;
int n , m , v , e;
int c[N] , d[N];
int dis[N][N];
double k[N];
double f[N][N][2];
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}

int main() {
    scanf("%d%d%d%d" , &n , &m , &v , &e);
    for(int i = 1 ; i <= n ; ++ i) c[i] = read();
    for(int i = 1 ; i <= n ; ++ i) d[i] = read();
    for(int i = 1 ; i <= n ; ++ i) scanf("%lf" , &k[i]);

    memset(dis , 127 / 3 , sizeof(dis));
    for(int i = 1 ; i <= v ; ++ i) dis[i][i] = 0;
    for(int i = 1 ; i <= e ; ++ i) {
        int a = read() , b = read() , w = read();
        if(dis[a][b] > w) {dis[a][b] = dis[b][a] = w;}
    }
    for(int k = 1 ; k <= v ; ++ k)
        for(int i = 1 ; i <= v ; ++ i)
            for(int j = 1 ; j <= v ; ++ j)
                dis[i][j] = min(dis[i][j] , dis[i][k] + dis[k][j]);
    
    for(int i = 1 ; i <= n ; ++ i) 
        for(int j = 0 ; j <= m ; ++ j)
            f[i][j][0] = f[i][j][1] = INF;
    f[1][1][1] = f[1][0][0] = 0.0;
    for(int i = 2 ; i <= n ; ++ i) {
        f[i][0][0] = f[i - 1][0][0] + dis[c[i - 1]][c[i]];
        for(int j = 1 ; j <= i && j <= m ; ++ j) {
            f[i][j][0] = min(
                f[i - 1][j][0]
                + dis[c[i - 1]][c[i]]
                ,
                f[i - 1][j][1]
                + k[i - 1] * dis[d[i - 1]][c[i]]
                + (1.0 - k[i - 1]) * dis[c[i - 1]][c[i]]
            );
            f[i][j][1] = min(
                f[i - 1][j - 1][0]
                + k[i] * dis[c[i - 1]][d[i]]
                + (1.0 - k[i]) * dis[c[i - 1]][c[i]]
                ,
                f[i - 1][j - 1][1]
                + k[i - 1] * k[i] * dis[d[i - 1]][d[i]]
                + (1.0 - k[i - 1]) * k[i] * dis[c[i - 1]][d[i]]
                + k[i - 1] * (1.0 - k[i]) * dis[d[i - 1]][c[i]]
                + (1.0 - k[i - 1]) * (1.0 - k[i]) * dis[c[i - 1]][c[i]]
            );
        }
    }
    double ans = f[n][0][0];
    for(int i = 0 ; i <= m ; ++ i) {
        ans = min(ans , f[n][i][0]);
        ans = min(ans , f[n][i][1]);
    }
    printf("%.2lf\n" , ans);
    return 0;
}
Comments

添加新评论