错是被学长挑出来的。。。QWQ@Monster_Yi
f[i][j][0/1] 为 第i天，换j次，换1/没换0
然后大力DP
#include<cstdio> #include<iostream> #include<cstring> #define R register int using namespace std; struct node{ int c,d; #define c(i) a[i].c #define d(i) a[i].d }a[10010]; int n,m,v,ee; long long e[310][310]; double k[2010],f[2010][2010][2],ans=1e17+10; inline void floyed() {for(R k=1;k<=v;++k) for(R i=1;i<=v;++i) for(R j=1;j<=v;++j) e[i][j]=min(e[i][j],e[i][k]+e[k][j]);} signed main() { scanf("%d%d%d%d",&n,&m,&v,&ee); for(R i=1;i<=n;++i) scanf("%d",&c(i)); for(R i=1;i<=n;++i) scanf("%d",&d(i)); for(R i=1;i<=n;++i) scanf("%lf",&k[i]); memset(e,0x3f,sizeof e); for(R i=1,u,vv,w;i<=ee;++i) scanf("%d%d%d",&u,&vv,&w),e[u][vv]=e[vv][u]=min(e[u][vv],(long long)w); for(R i=1;i<=v;++i) e[i][i]=0; floyed(); //for(R i=1;i<=v;++i,cout<<endl)for(R j=1;j<=v;++j) cout<<e[i][j]<<" "; for(R i=0;i<=n;++i) for(R j=0;j<=n;++j) f[i][j][1]=f[i][j][0]=1e17+10; f[1][0][0]=f[1][1][1]=0; for(R i=2;i<=n;++i) { f[i][0][0]=f[i-1][0][0]+e[c(i)][c(i-1)]; for(R j=1;j<=min(i,m);++j){ f[i][j][0]=min(f[i][j][0],min(f[i-1][j][0]+e[c(i)][c(i-1)],f[i-1][j][1]+k[i-1]*e[c(i)][d(i-1)]+(1-k[i-1])*e[c(i)][c(i-1)])); f[i][j][1]=min(f[i][j][1],min(f[i-1][j-1][0]+k[i]*e[d(i)][c(i-1)]+(1-k[i])*e[c(i)][c(i-1)], f[i-1][j-1][1]+k[i-1]*k[i]*e[d(i)][d(i-1)]+(1-k[i])*(1-k[i-1])*e[c(i)][c(i-1)]+k[i]*(1-k[i-1])*e[d(i)][c(i-1)]+(1-k[i])*k[i-1]*e[c(i)][d(i-1)])); } } for(R i=0;i<=m;++i) ans=min(min(f[n][i][0],f[n][i][1]),ans);//,cout<<f[n][i][0]<<" "<<f[n][i][1]<<endl; printf("%.2lf ",ans); }
2019.04.07