[NOIP2016]换教室

换教室

这种有某个不定值求最佳情况感觉还是动态规划，但最重要的是找好迭代关系（公式太长，看代码吧）

然后就是求两个点之间耗费体力最少的路的耗费值，数据大小是300，可以使用floyed

//https://ac.nowcoder.com/acm/problem/16428
#include
#define LOCAL
using namespace std;
const int maxn=2010;
const int INF=9e6+10;// 两个点之间耗费体力值之和的最小值
int c[maxn],d[maxn];
double k[maxn];
double dp[maxn][maxn][2];
int mm[305][305];
void floyed(int v){
    for (int k=1;k<=v;++k){
        for (int i=1;i<=v;++i){
            for (int j=i+1;j<=v;++j){
                mm[i][j]=min(mm[i][j],mm[i][k]+mm[k][j]);
                mm[j][i]=mm[i][j];
            }
            // for (int j=1;j<=v;++j){
            //     mm[i][j]=min(mm[i][j],mm[i][k]+mm[k][j]);
            // }
        }
    }
}

int main(){
    #ifdef LOCAL
    freopen("input.txt","r",stdin);
    #endif
    std::ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m,v,e;
    cin>>n>>m>>v>>e;
    for (int i=1;i<=n;++i) cin>>c[i];
    for (int i=1;i<=n;++i) cin>>d[i];
    for (int i=1;i<=n;++i) cin>>k[i];
    for (int i=1;i<=v;++i) mm[i][i]=0;
    for (int i=1;i<=v;++i) for (int j=i+1;j<=v;++j) {
        mm[i][j]=INF;
        mm[j][i]=INF;
    }
    for (int i=1;i<=e;++i){
        int a,b,w;
        cin>>a>>b>>w;
        mm[a][b]=min(mm[a][b],w);
        mm[b][a]=mm[a][b];
    }
    floyed(v);
    for (int i=1;i<=n;++i) for (int j=0;j<=m;++j) dp[i][j][0]=dp[i][j][1]=INF;
    // 下面这句错了！ 首先dp[1][0][1]是非法的，但它在后面会被用到，所以他要被置为INF
    // 然后从本质上讲，只有dp[1][0][0],dp[1][1][0/1]以及上面那个非法的会被用到，所以其余三个为零
    // for (int i=0;i<=m;++i) dp[1][i][0]=dp[1][i][1]=0;
    dp[1][0][0]=0;dp[1][1][1]=0;dp[1][1][0]=0;
    for (int i=2;i<=n;++i){
        for (int j=0;j<=m;++j){
            dp[i][j][0]=min(dp[i-1][j][0]+mm[c[i-1]][c[i]],dp[i-1][j][1]+mm[d[i-1]][c[i]]*k[i-1]+mm[c[i-1]][c[i]]*(1-k[i-1]));
            if (j) dp[i][j][1]=min(dp[i-1][j-1][0]+mm[c[i-1]][d[i]]*k[i]+mm[c[i-1]][c[i]]*(1-k[i]),dp[i-1][j-1][1]+mm[c[i-1]][c[i]]*(1-k[i-1])*(1-k[i])+mm[c[i-1]][d[i]]*(1-k[i-1])*k[i]+mm[d[i-1]][c[i]]*k[i-1]*(1-k[i])+mm[d[i-1]][d[i]]*k[i-1]*k[i]);
        }
    }
    // double ans=min(dp[n][m][0],dp[n][m][1]);
    double ans=INF;
    for (int i=0;i<=m;++i) {
        double tmpans=min(dp[n][i][0],dp[n][i][1]);
        ans=min(ans,tmpans);
    }
    printf("%.2lf",ans);
    return 0;
}