【luogu P1850 换教室】题解

题目链接：https://www.luogu.org/problemnew/show/P1850

难的不在状态上，难在转移方程。

（话说方程写错居然还有84分= =）

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define ll long long

using namespace std;

const ll maxn = 2010;

ll n, m, v, e, c[maxn], d[maxn], u[maxn][maxn], a, b, w;

double k[maxn], l[maxn], dp[maxn][maxn][2], ans = 1e9;

int main()

{

    //freopen("change.in","r",stdin);

    ios::sync_with_stdio(false);

    memset(u, 63, sizeof(u));

    memset(dp, 127, sizeof(dp));

    cin>>n>>m>>v>>e;

    for(ll i = 1; i <= n; i++)

    cin>>c[i];

    for(ll i = 1; i <= n; i++)

    cin>>d[i];

    for(ll i = 1; i <= n; i++)

    {cin>>k[i]; l[i] = 1-k[i];}

    for(ll i = 1; i <= e; i++)

    {

        cin>>a>>b>>w;

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

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

    }

    for(ll q = 1; q <= v; q++)

        for(ll i = 1; i <= v; i++)

            for(ll j = 1; j <= v; j++)

            if(i != q && j != q && i != j) u[i][j] = min(u[i][j], u[i][q] + u[q][j]);

    for(ll i = 1; i <= v; i++) u[i][i] = u[i][0] = u[0][i] = 0;

    dp[1][0][0] = dp[1][1][1] = 0;

    for(ll i = 2; i <= n; i++)

    {

        ll x1 = c[i], x2 = c[i-1], y1 = d[i], y2 = d[i-1];

        dp[i][0][0] = dp[i-1][0][0] + u[x2][x1];

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

        {

            dp[i][j][0] = min(dp[i][j][0], min(dp[i-1][j][0] + u[x2][x1], dp[i-1][j][1] + l[i-1] * u[x2][x1] + k[i-1] * u[y2][x1]));

            dp[i][j][1] = min(dp[i][j][1], min(dp[i-1][j-1][0] + u[x2][x1] * l[i] + u[x2][y1] * k[i], dp[i-1][j-1][1] + k[i-1] * l[i] * u[y2][x1] + l[i] * l[i-1] * u[x2][x1] + k[i] * k[i-1] * u[y2][y1] + l[i-1] * k[i] * u[x2][y1]));

        }

    }

    for(ll i = 0; i <= m; i++)

    ans = min(ans, min(dp[n][i][0], dp[n][i][1]));

    printf("%0.2lf",ans);

    return 0;

}

巴特西

【luogu P1850 换教室】题解

最新文章

热门文章

巴特西

【luogu P1850 换教室】 题解

最新文章

热门文章

【luogu P1850 换教室】题解