NOIP2016换教室

题目传送门
md考场上xjb写完了暴力还™写错了，据说暴力分共76分啊，我却只有20分。

不管了tmd
设$f[i][j][1/0]$表示前i节课，申请了j次，这一次申请/不申请的总耗费体力值期望的最小值。
显然对于这一次，申请/不申请，有两种情况，就是上一次申请和上一次不申请。
状态转移方程暴力推就好，注意这一次和上一次申请通过和不通过是两种情况。
也就是从哪个教室到哪个教室都不确定的，体力花费值根据期望的定义算。
算了直接放代码

/*
Author: CNYALI_LK
LANG: C++
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define up(a,b,c) for (int a(b),end##a(c);a<=end##a;++a)
#define down(a,c,b) for (int a(b),end##a(c);a>=end##a;--a)
#define uup(a,c,b) for (int a(b),end##a(c);a<=end##a;++a)
#define udown(a,b,c) for (int a(b),end##a(c);a>=end##a;--a)
#define endl '\n'
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
struct inout{
//  输入输出略。
};
inout io;
int c[2333],d[2333];
double f[2333][2333][2],k[2333];
int a[345][345];
template<class T>void chkmin(T &a,T b){a=a<b?a:b;}
int main(){
#ifdef cnyali_lk
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    io.init();
    int n,m,v,e,u,wea,w;
    io>>n>>m>>v>>e;
    up(i,1,n){
        io>>c[i];
    }
    up(i,1,n)io>>d[i];
    up(i,1,n)io>>k[i];
    up(i,1,v)up(j,i+1,v)a[i][j]=a[j][i]=0x3f3f3f3f;
    up(i,1,e){
        io>>u>>wea>>w;
        chkmin(a[u][wea],w);
        chkmin(a[wea][u],w);
    }
    up(k,1,v)up(i,1,v)up(j,1,v)chkmin(a[i][j],a[i][k]+a[k][j]);
    //注意是v个教室！v个教室！v个教室！！！！！！！

    up(i,1,m)f[0][i][0]=f[0][i][1]=0;
    up(i,1,n){
        f[i][0][0]=f[i-1][0][0]+a[c[i-1]][c[i]];
        f[i][0][1]=1e10;
        up(j,1,m){
            f[i][j][0]=min(f[i-1][j][0]+a[c[i]][c[i-1]],f[i-1][j][1]+k[i-1]*a[d[i-1]][c[i]]+(1-k[i-1])*a[c[i-1]][c[i]]);//暴力转移
            f[i][j][1]=min(
                f[i-1][j-1][0]+k[i]*a[c[i-1]][d[i]]+(1-k[i])*a[c[i-1]][c[i]],
                f[i-1][j-1][1]+k[i]*k[i-1]*a[d[i-1]][d[i]]+
                (1-k[i])*k[i-1]*a[d[i-1]][c[i]]+k[i]*(1-k[i-1])*a[c[i-1]][d[i]]+(1-k[i-1])*(1-k[i])*a[c[i-1]][c[i]]
            );//更暴力的转移
        }
    }
    double ans=1e9;
    up(i,0,m){
        chkmin(ans,f[n][i][1]);
        chkmin(ans,f[n][i][0]);
    }
    printf("%.2lf\n",ans);
    return 0;
}