** CCF简直不安好心,考试时第一眼就看到了黑体下划线加粗的”期望值”三个字,吓得我直接写了个100+行的暴力…考完以后一想,这题好像可做啊…啊,看来还是我比较naïve.
做这道题首先要知道期望是可以线性递推的(不明白的可以自己推式子展开一下或者自行百度),然后就可以DP了.这道题的DP类似与背包,我们用DP[i][j]表示当前考虑完前i门课程,其中申请了j门的方案数.因为申请可能失败,从c[i]与d[i]转移的距离不一样,所以还要再加一维[0/1]表示当前走到的是c[i]还是d[i].转移方程分类讨论一下:上一个申不申请,这一个申不申请,总共2*2=4种情况.最后再Floyd预处理出两两的最短路就搞定了.
代码不到50行…求我的心理阴影面积…
附代码：**

#include<bits/stdc++.h>
#define inf 1000000007
using namespace std;

int n,m,v,e,c[2005],d[2005],dis[305][305];
double k[2005],dp[2005][2005][2],ans=1.0*inf;

int main(){
    for(int i=0;i<=304;i++)
        for(int j=0;j<=304;j++)
            dis[i][j]=inf;
    for(int i=0;i<=304;i++) dis[i][i]=0;//pre
    scanf("%d%d%d%d",&n,&m,&v,&e);
    for(int i=1;i<=n;i++) scanf("%d",&c[i]);
    for(int i=1;i<=n;i++) scanf("%d",&d[i]);
    for(int i=1;i<=n;i++) cin>>k[i];
    for(int i=1;i<=e;i++){
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        dis[x][y]=dis[y][x]=min(dis[x][y],w);
    }
    for(int l=1;l<=v;l++)
        for(int i=1;i<=v;i++)
            for(int j=1;j<=v;j++)
                dis[i][j]=min(dis[i][j],dis[i][l]+dis[l][j]);//floyd            
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            dp[i][j][0]=dp[i][j][1]=1.0*inf;
    dp[1][0][0]=dp[1][1][1]=0;
    for(int i=2;i<=n;i++)
        for(int j=0;j<=min(i,m);j++){
            dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][0]+dis[c[i-1]][c[i]]);
            dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][1]+k[i-1]*dis[d[i-1]][c[i]]+(1.0-k[i-1])*dis[c[i-1]][c[i]]);
            if(j>0){
                dp[i][j][1]=min(dp[i][j][1],dp[i-1][j-1][0]+k[i]*dis[c[i-1]][d[i]]+(1.0-k[i])*dis[c[i-1]][c[i]]);
                dp[i][j][1]=min(dp[i][j][1],dp[i-1][j-1][1]
                                            +k[i-1]*k[i]*dis[d[i-1]][d[i]]
                                            +k[i-1]*(1.0-k[i])*dis[d[i-1]][c[i]]
                                            +(1.0-k[i-1])*k[i]*dis[c[i-1]][d[i]]
                                            +(1.0-k[i-1])*(1.0-k[i])*dis[c[i-1]][c[i]]);
            }
        }
    for(int i=0;i<=m;i++) ans=min(ans,min(dp[n][i][0],dp[n][i][1]));
    printf("%.2lf",ans);
    return 0;                   
}

dp[i][j][0]表示前i天j个换教室且第i天不申请，dp[i][j][1]第i天申请.
转移时把状态表示完。
floyed预处理最短路。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#define LL long long 
using namespace std;
template <class _T> inline void read(_T &_x) {
    int _t; bool _flag=false;
    while((_t=getchar())!='-'&&(_t<'0'||_t>'9')) ;
    if(_t=='-') _flag=true,_t=getchar(); _x=_t-'0';
    while((_t=getchar())>='0'&&_t<='9') _x=_x*10+_t-'0';
    if(_flag) _x=-_x;
}
const int maxn=305;
const int MAXN=2005;
const double inf=0x3f3f3f3f;
int n,m,v,e,x,y,z;
int C[MAXN],D[MAXN],head[maxn],dis[maxn][maxn];
double K[MAXN],dp[MAXN][MAXN][2];
int main(){
    read(n),read(m),read(v),read(e);
    for(int i=1;i<=n;i++){
        read(C[i]);
    } 
    for(int i=1;i<=n;i++){
        read(D[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%lf",&K[i]);
    }
    for(int i=1;i<=v;i++){
        for(int j=1;j<=v;j++){
            if(i!=j)dis[i][j]=inf;
        }
    }
    for(int i=1;i<=e;i++){
        read(x),read(y),read(z); 
        dis[x][y]=dis[y][x]=min(dis[x][y],z);
    }
    for(int k=1;k<=v;k++){
        for(int i=1;i<=v;i++){
            for(int j=1;j<=v;j++){
                if(i!=k&&j!=k&&i!=j)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++)
            dp[i][j][1]=dp[i][j][0]=inf;
    }
    dp[1][0][0]=dp[1][1][1]=0;
    for(int i=2;i<=n;i++){
        for(int j=0;j<=m&&j<=i;j++){
            if(j>0)dp[i][j][1]=min(dp[i-1][j-1][0]+K[i]*dis[C[i-1]][D[i]]+(1-K[i])*dis[C[i-1]][C[i]],dp[i-1][j-1][1]+K[i]*K[i-1]*dis[D[i-1]][D[i]]+(1-K[i])*K[i-1]*dis[D[i-1]][C[i]]+(1-K[i-1])*K[i]*dis[C[i-1]][D[i]]+(1-K[i])*(1-K[i-1])*dis[C[i-1]][C[i]]);
            dp[i][j][0]=min(dp[i-1][j][0]+dis[C[i-1]][C[i]],dp[i-1][j][1]+K[i-1]*dis[D[i-1]][C[i]]+(1-K[i-1])*dis[C[i-1]][C[i]]);
        }
    }
    double ans=inf;
    for(int i=0;i<=m;i++){
        ans=min(dp[n][i][1],min(ans,dp[n][i][0]));
    }
    printf("%.2lf",ans);
    return 0;
}

dp[x][k][b]表示前x个时间点申请k次换教室的最小期望总代价，b=0表示第x个不申请，b=1表示第x个申请换教室。（原题貌似是“时间段”来着）
求dp[x][k][1]时应该是分两种情况然后取最小值：一是dp[x-1][k-1][0]，也就是上一个时间点不申请，二是dp[x-1][k-1][1]，也就是上一个时间点申请。
然而我一开始把这里搞错了，我按当前这一次成功还是失败分了两种情况（也就是solve()函数里那一片注释掉的代码），然而这样的话转移过程就会有矛盾。如果这一次成功的dpSucc来自于dp[x-1][k-1][0]，这一次失败的dpFail来自于dp[x-1][k-1][0]，这样转移关系就混乱了。
不过这样写居然也能拿88分，害得我一开始还以为是精度误差-_-||（当然这是我的锅啦）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <numeric>

const int maxN = 2000 + 5;
const int maxV = 300 + 5;

int dist[maxV][maxV];
int C[maxN], D[maxN]; //C[i]: id of classroom before changing, D[i]: after changing
double K[maxN]; //K[i]: probability of changing at i-th time point
int N, M, V, E; //N time points, M applications at most, V classrooms, E ways

void input()
{
    scanf("%d%d%d%d", &N, &M, &V, &E);

    auto readint = [] (int& val) -> void {
        scanf("%d", &val);
    };
    std::for_each(C + 1, C + N + 1, readint);
    std::for_each(D + 1, D + N + 1, readint);

    for (int i = 1; i <= N; i++)
        scanf("%lf", K + i);

    memset(dist, 0x3f, sizeof(dist));
    for (int i = 1; i <= V; i++)
        dist[i][i] = 0;

    for (int u, v, w, i = 0; i < E; i++)
    {
        scanf("%d%d%d", &u, &v, &w);
        dist[u][v] = dist[v][u] = std::min(dist[u][v], w);
    }
}

void floyd()
{
    for (int k = 1; k <= V; k++)
        for (int i = 1; i <= V; i++)
            //for (int j = i + 1; j <= V; j++)
            for (int j = 1; j < i; j++)
                dist[i][j] = dist[j][i] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
}

double dp[maxN][maxN][2];
//dp[x][k][0]: first x time points, k applications, not apply for the x-th time point
//dp[x][k][1]: apply for the x-th time point

///@param id: current time point, id >= 2 should be guaranteed
///@param f1: true if last time point has an application, false if not
///@param f2: true if current time point has a change (suppose the change indeed happens)
template<bool f1, bool f2>
double getDist(int id)
{
    int curV = (f2 ? D[id] : C[id]);
    if (f1)
        return K[id - 1] * dist[D[id - 1]][curV] + (1.0 - K[id - 1]) * dist[C[id - 1]][curV];
    //K[id - 1] probability that application for (id - 1)-th time point succeeds
    return dist[C[id - 1]][curV];
}

double solve()
{
    floyd();

    std::fill_n((double*)dp, maxN * maxN * 2, 1e20);
    dp[1][0][0] = 0.0;
    dp[1][1][1] = (M > 0 ? 0.0 : 1e20);

    for (int x = 2; x <= N; x++)
    {
        dp[x][0][0] = dp[x - 1][0][0] + getDist<false, false>(x);
        for (int k = 1; k <= M && k <= x; k++)
        {
            dp[x][k][0] = std::min(dp[x - 1][k][0] + getDist<false, false>(x),
                                   dp[x - 1][k][1] + getDist<true, false>(x));
//            //if current application succeeds
//            double dpSucc = K[x] * std::min(dp[x - 1][k - 1][0] + getDist<false, true>(x),
//                                            dp[x - 1][k - 1][1] + getDist<true, true>(x));
//            //if fails
//            double dpFail = (1.0 - K[x]) * std::min(dp[x - 1][k - 1][0] + getDist<false, false>(x),
//                                                    dp[x - 1][k - 1][1] + getDist<true, false>(x));
            //if last time point has no application
            double dp0 = dp[x - 1][k - 1][0] +
                    (K[x] * getDist<false, true>(x) + (1.0 - K[x]) * getDist<false, false>(x));
            //if last time has an application
            double dp1 = dp[x - 1][k - 1][1] +
                    (K[x] * getDist<true, true>(x) + (1.0 - K[x]) * getDist<true, false>(x));

            dp[x][k][1] = std::min(dp0, dp1);
        }
    }

    double ans = 1e20;
    for (int k = 0; k <= M; k++)
        ans = std::min({ans, dp[N][k][0], dp[N][k][1]});

    return ans;
}

int main()
{
    input();
    printf("%.2f", solve());
    return 0;
}

好说，好说
学习神犇的代码
努力成为神犇

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
template<class T> inline void read(T &_a){
    bool f=0;int _ch=getchar();_a=0;
    while(_ch<'0' || _ch>'9'){if(_ch=='-')f=1;_ch=getchar();}
    while(_ch>='0' && _ch<='9'){_a=(_a<<1)+(_a<<3)+_ch-'0';_ch=getchar();}
    if(f)_a=-_a;
}

const int maxn=2001,maxm=2001;
int n,m,v,e,dis[301][301],c[maxn],d[maxn];
double k[maxn],dp[maxn][maxn][2];

int main()
{
    read(n); read(m); read(v); read(e);
    for (register int i=1;i<=n;++i) read(c[i]); 
    for (register int i=1;i<=n;++i) read(d[i]);
    for (register int i=1;i<=n;++i) scanf("%lf",&k[i]);
    memset(dis,0x3f,sizeof(dis));   // 如果是0x7f，那么在之后的状态转移中会算爆int，直接GG
    for (register int i=1,a,b,w;i<=e;++i)
    {
        read(a); read(b); read(w);
        dis[b][a]=dis[a][b]=min(dis[a][b],w);
    }
    for (register int i=0;i<=v;++i) dis[i][i]=dis[0][i]=0;
    for (register int i=1;i<=v;++i)
        for (register int j=1;j<=v;++j)
            for (register int k=1;k<=v;++k)
                if(i!=j&&j!=k&&k!=i)
                    dis[j][k]=min(dis[j][k],dis[j][i]+dis[i][k]);
    memset(dp,0x7f,sizeof(dp));
    dp[1][0][0]=dp[1][1][1]=0;
    for (register int i=2;i<=n;++i)
        for (register int j=0;j<=m&&j<=i;++j)
        {
            dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][0]+dis[c[i-1]][c[i]]);
            dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][1]+k[i-1]*dis[d[i-1]][c[i]]+(1.0-k[i-1])*dis[c[i-1]][c[i]]);
            if(j==0) continue;
            dp[i][j][1]=min(dp[i][j][1],dp[i-1][j-1][0]+k[i]*dis[c[i-1]][d[i]]+(1.0-k[i])*dis[c[i-1]][c[i]]);
            dp[i][j][1]=min(dp[i][j][1],dp[i-1][j-1][1]+k[i-1]*k[i]*dis[d[i-1]][d[i]]+k[i-1]*(1.0-k[i])*dis[d[i-1]][c[i]]+(1.0-k[i-1])*k[i]*dis[c[i-1]][d[i]]+(1.0-k[i-1])*(1.0-k[i])*dis[c[i-1]][c[i]]);
        }
    double ans=0x7fffffff;
    for (register int i=0;i<=m;++i) ans=min(ans,min(dp[n][i][0],dp[n][i][1]));
    printf("%.2lf",ans);
    return 0;
}

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m,v,e;
int c[2000+1];
int d[2000+1];
double p[2000+1];
double f[2000+1][2000+1][1+1];
double dis[300+1][300+1];

int main()
{
    while (~scanf("%d%d%d%d",&n,&m,&v,&e))
    {
        for (int i=1;i<=n;i++)
            scanf("%d",&c[i]);
        for (int i=1;i<=n;i++)
            scanf("%d",&d[i]);
        for (int i=1;i<=n;i++)
            scanf("%lf",&p[i]);
        for (int i=1;i<=v;i++)
            for (int j=1;j<=v;j++)
                dis[i][j]=oo_max;
        for (int i=1;i<=v;i++)
            dis[i][i]=0;
        for (int i=1;i<=e;i++)
        {
            int x,y;
            double w;
            scanf("%d%d%lf",&x,&y,&w);
            dis[x][y]=dis[y][x]=min(min(dis[x][y],dis[y][x]),w);
        }
        for (int i=1;i<=v;i++)
            for (int j=1;j<=v;j++)
                for (int k=1;k<=v;k++)
                    dis[j][k]=min(dis[j][k],dis[j][i]+dis[i][k]);
        for (int i=1;i<=n;i++)
            for (int j=0;j<=m;j++)
                f[i][j][0]=f[i][j][1]=oo_max;
        f[1][0][0]=f[1][1][1]=0;
        for (int i=2;i<=n;i++)
            for (int j=0;j<=min(i,m);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]+(p[i-1]*dis[d[i-1]][c[i]])+((1-p[i-1])*dis[c[i-1]][c[i]]));
                if (j>0)
                {
                    f[i][j][1]=min(f[i][j][1],f[i-1][j-1][0]+(p[i]*dis[c[i-1]][d[i]])+((1-p[i])*dis[c[i-1]][c[i]]));
                    f[i][j][1]=min(f[i][j][1],f[i-1][j-1][1]+((p[i-1]*p[i])*dis[d[i-1]][d[i]])+((p[i-1]*(1-p[i]))*dis[d[i-1]][c[i]])+(((1-p[i-1])*p[i])*dis[c[i-1]][d[i]])+(((1-p[i-1])*(1-p[i]))*dis[c[i-1]][c[i]]));
                }
            }
        double ans=oo_max;
        for (int i=0;i<=m;i++)
            ans=min(ans,min(f[n][i][0],f[n][i][1]));
        printf("%.2lf\n",ans);
    }
}

Floyd+DP。一定要注意重边，否则只有40分

#include <cstdio>
#include <algorithm>

using namespace std;

long long dist[301][301];
double f[2001][2001][2];

int c[2001];
int d[2001];
double K[2001];

int n, m, v, e;

const int INF = 1000000000;

int main()
{
    int i, j, k;
    scanf("%d%d%d%d", &n, &m, &v, &e);
    for (i = 1; i <= n; i++) {
        scanf("%d", c + i);
    }
    for (i = 1; i <= n; i++) {
        scanf("%d", d + i);
    }
    for (i = 1; i <= n; i++) {
        scanf("%lf", K + i);
    }
    /* Floyd */
    for (i = 1; i <= v; i++) {
        for (j = 1; j <= v; j++) {
            if (i == j)
                dist[i][j] = 0;
            else
                dist[i][j] = INF;
        }
    }
    for (i = 1; i <= e; i++) {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        dist[a][b] = min(dist[a][b], w);
        dist[b][a] = min(dist[b][a], w);
    }
    for (i = 1; i <= v; i++) {
        for (j = 1; j <= v; j++) {
            for (k = 1; k <= v; k++) {
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }
    
    for (i = 0; i <= 2000; i++) {
        for (j = 0; j <= 2000; j++) {
            f[i][j][0] = INF;
            f[i][j][1] = INF;
        }
    }
    
    f[1][0][0] = 0;
    f[1][1][1] = 0;
    
    for (i = 2; i <= n; i++) {
        for (j = 0; j <= i && j <= m; j++) {
            if (j != 0) {
                f[i][j][1] = f[i - 1][j - 1][0]
                    + K[i] * dist[c[i - 1]][d[i]] + (1 - K[i]) * dist[c[i - 1]][c[i]];
                if (j > 1) f[i][j][1] = min(f[i][j][1], f[i - 1][j - 1][1] + K[i - 1]  *      K[i]  * dist[d[i - 1]][d[i]]
                                     + (1 - K[i - 1]) *      K[i]  * dist[c[i - 1]][d[i]]
                                     +      K[i - 1]  * (1 - K[i]) * dist[d[i - 1]][c[i]]
                                     + (1 - K[i - 1]) * (1 - K[i]) * dist[c[i - 1]][c[i]]);
            }
            f[i][j][0] = f[i - 1][j][0] + dist[c[i - 1]][c[i]];
            if (j != 0) f[i][j][0] = min(f[i][j][0], f[i - 1][j][1] + K[i - 1]  * dist[d[i - 1]][c[i]]
                                     + (1 - K[i - 1]) * dist[c[i - 1]][c[i]]);
        }
    }
    double ans = INF;
    for (i = 0; i <= m; i++) {
        if (i == 0)
            ans = f[n][0][0];
        else
            ans = min(ans, min(f[n][i][0], f[n][i][1]));
    }
    printf("%.2lf", ans);
    return 0;
}

不难但很繁的一道题qwq

#include<bits/stdc++.h>
using namespace std;

const double inf=987654321.0;
int c[2005], d[2005], dis[305][305];
double k[2005], f[2005][2005][2], ans=inf;

int main()
{
    memset(dis, 0x3f, sizeof(dis));
    int n, m, v, e; cin>>n>>m>>v>>e;
    for(int i=1;i<=n;i++) scanf("%d", &c[i]);
    for(int i=1;i<=n;i++) scanf("%d", &d[i]);
    for(int i=1;i<=n;i++) scanf("%lf", &k[i]);
    for(int i=1;i<=v;i++) dis[i][i]=0;
    for(int i=1;i<=e;i++){
            int a, b, w;
            scanf("%d%d%d", &a, &b, &w);
            if(w>=dis[a][b]) continue;
            dis[a][b]=dis[b][a]=w;
    }
    for(int l=1;l<=v;l++)
            for(int i=1;i<=v;i++)
                    for(int j=1;j<=v;j++)
                            dis[i][j]=min(dis[i][j], dis[i][l]+dis[l][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][0][0]=f[1][1][1]=0.0;
    for(int i=2;i<=n;i++)
            for(int j=min(i, m);j>=0;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-k[i-1])*dis[c[i-1]][c[i]]); 
                    if(j>0)
                            f[i][j][1]=min(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-1][j-1][1]+k[i-1]*(k[i]*dis[d[i-1]][d[i]]+(1-k[i])*dis[d[i-1]][c[i]])+(1-k[i-1])*(k[i]*dis[c[i-1]][d[i]]+(1-k[i])*dis[c[i-1]][c[i]]));
            }               
    for(int i=0;i<=min(i, m);i++) ans=min(ans, min(f[n][i][0], f[n][i][1]));
    printf("%.2lf\n", ans);  
    return 0;
}

http://www.cnblogs.com/937337156Zhang/p/6444896.html
C++题解+代码

http://www.cnblogs.com/937337156Zhang/p/6444896.html
C++题解+代码O(∩_∩)O谢谢！

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define N 2005

int n,m,v,e,x,y;
int c[N],d[N];
double z,inf,kk[N],sdis[N],dis[N][N],f[N][N][2],ans;

void floyed()
{
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]);
}
int main()
{

scanf("%d%d%d%d",&n,&m,&v,&e);
for (int i=1;i<=n;++i) scanf("%d",&c[i]);
for (int i=1;i<=n;++i) scanf("%d",&d[i]);
for (int i=1;i<=n;++i) scanf("%lf",&kk[i]);
memset(dis,127,sizeof(dis));inf=dis[0][0];
for (int i=1;i<=v;++i) dis[i][i]=0.0;
for (int i=1;i<=e;++i)
{
scanf("%d%d%lf",&x,&y,&z);
dis[x][y]=dis[y][x]=min(dis[x][y],z);
}
floyed();memset(f,127,sizeof(f));
/*
for (int i=1;i<=v;++i)
for (int j=i;j<=v;++j)
printf("%d %d %.2lf\n",i,j,dis[i][j]);
puts("");
/
for (int i=2;i<=n;++i)
ans+=dis[c[i-1]][c[i]];
f[1][0][0]=f[1][1][1]=0.0;
for (int i=1;i<n;++i)
for (int j=0;j<=min(i,m);++j)
{
if (f[i][j][0]!=inf)
{
f[i+1][j][0]=min(f[i+1][j][0],f[i][j][0]+dis[c[i]][c[i+1]]);
if (j<m) f[i+1][j+1][1]=min(f[i+1][j+1][1],f[i][j][0]+dis[c[i]][c[i+1]](1-kk[i+1])+dis[c[i]][d[i+1]]*kk[i+1]);
}
if (f[i][j][1]!=inf)
{
f[i+1][j][0]=min(f[i+1][j][0],f[i][j][1]+dis[c[i]][c[i+1]]*(1-kk[i])+dis[d[i]][c[i+1]]*kk[i]);
if (j<m) f[i+1][j+1][1]=min(f[i+1][j+1][1],f[i][j][1]+(1-kk[i])*(1-kk[i+1])*dis[c[i]][c[i+1]]+(1-kk[i])*kk[i+1]*dis[c[i]][d[i+1]]+kk[i]*(1-kk[i+1])*dis[d[i]][c[i+1]]+kk[i]*kk[i+1]*dis[d[i]][d[i+1]]);
}
}
for (int i=0;i<=m;++i) ans=min(ans,min(f[n][i][0],f[n][i][1]));
printf("%0.2lf\n",ans);
return 0;
}
应该是对的。。。