期望与现实总是背道而驰

懵逼的 题目

传送至 UOJ

扯淡的 题解

一开始设的状态比较鬼畜然后发现不会转移了…
一开始设的f[i][j][0 / 1]代表在 i 时间段, 已经用了 j 次交换, 0 代表在 c 教室, 1 代表在 d 教室, 的最小期望
然后…发现就玩不转了…样例还能过差评
因为不能知道当前的申请能否通过
然后就扔了…
今天翻到menci的blog发现这道题的题解…才不是抄题解呐
Menci的题解(无限敬仰Orz)
发现状态可以表示成: 0 代表没有申请, 1 代表申请了的最小期望
然后就可以转移了…

沙茶的 代码

突然发现我没四舍五入也过了 辣鸡数据

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define MAXN (300 + 5)
#define MAXM (90000 + 5)
#define MAXT (2000 + 5)
#define MAXC (2000 + 5)
#define INF (0x7ffffff)
#define DD double
using namespace std;
int n, m;
int dis[MAXN][MAXN];
int ti, ch;
int c[MAXT];
int d[MAXT];
DD k[MAXT];
DD f[MAXT][MAXT][2];// f[i][j][0 / 1]: 当前在 i 时间段, 已经申请了 j 次, [0 / 1]: 当前是否申请 
DD ans = INF;

void init();
void floyd();
void dp();
int main()
{
    init();
    floyd();
    dp();
    printf("%.2lf", ans);
    return 0;
}

void init()
{
    memset(dis, 0x7f, sizeof(dis));
    memset(f, 0x7f,sizeof(f));
    scanf("%d%d%d%d", &ti, &ch, &n, &m);
    for (int i = 1; i <= ti; i++)
    {
        scanf("%d", &c[i]);
    }
    for (int i = 1; i <= ti; i++)
    {
        scanf("%d", &d[i]);
    }
    for (int i = 1; i <= ti; i++)
    {
        scanf("%lf", &k[i]);
    }
    int srx, sry, srz;
    for (int i = 1; i <= n; i++)
    {
        dis[i][i] = 0;
    }
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &srx, &sry, &srz);
        dis[sry][srx] = dis[srx][sry] = min(dis[srx][sry], srz);
    }
}

void floyd()
{
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (i != j && j != k && k != i && dis[i][k] < INF && dis[k][j] < INF)
                {
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
                }
            }
        }
    }
}

void dp()
{
    f[1][0][0] = 0;
    f[1][1][1] = 0;
    c[0] = d[0] = 0;
    dis[0][c[0]] = dis[0][c[1]] = dis[0][d[0]] = dis[0][d[1]] = 0;
    for (int i = 2; i <= ti; i++)
    {
        f[i][0][0] = f[i - 1][0][0] + dis[c[i - 1]][c[i]];
        f[i][0][1] = INF;
        for (int j = 1; j <= min(ch, i); j++)
        {
            f[i][j][0] = min(f[i][j][0], f[i - 1][j][0] + dis[c[i - 1]][c[i]]);
            f[i][j][0] = min(f[i][j][0], f[i - 1][j][1] + (dis[d[i - 1]][c[i]] * k[i - 1]) + (dis[c[i - 1]][c[i]] * (1 - k[i - 1])));
            f[i][j][1] = min(f[i][j][1], f[i - 1][j - 1][0] + (k[i] * dis[c[i - 1]][d[i]]) + ((1 - k[i]) * dis[c[i - 1]][c[i]]));
            f[i][j][1] = min(f[i][j][1], f[i - 1][j - 1][1] + (k[i] * k[i - 1] * dis[d[i - 1]][d[i]]) + ((1 - k[i - 1]) * k[i] * dis[c[i - 1]][d[i]]) + (k[i - 1] * (1 - k[i]) * dis[d[i - 1]][c[i]]) + ((1 - k[i - 1]) * (1 - k[i]) * dis[c[i - 1]][c[i]]));
//            if (f[i][j][0] < INF)
//            printf("%d %d %d: %.2lf\n", i, j, 0, f[i][j][0]);
//            if (f[i][j][1] < INF)
//            printf("%d %d %d: %.2lf\n", i, j, 1, f[i][j][1]);
        }
    }
    for (int i = 0; i <= ch; i++)
    {
        ans = min(ans, f[ti][min(i, ti - 1)][0]);
        ans = min(ans, f[ti][min(i, ti)][1]);
    }
}
/*
3 2 3 3
2 1 2
1 2 1
0.8 0.2 0.5
1 2 5
1 3 3
2 3 1
*/

By 脑子抽风的 Cansult