[NOIP2016]换教室 期望dp

先弗洛伊德，然后把状态拆分遗传

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define f(a,b,c) g[a+10][b+10][c+1]
#define N 2100
#define M 320 
using namespace std;
typedef double D;
int d[M][M],c[N][5];
D g[N][N][5];
int n,m,v,e;
D w[N];
inline int MIN(int x,int y)
{
  return x<y?x:y;
}
inline D Min(D x,D y)
{
  return x<y?x:y;
}
int main()
{
  freopen("classrooma.in","r",stdin);
  freopen("classrooma.out","w",stdout);
  scanf("%d%d%d%d",&n,&m,&v,&e);
  for(int i=1;i<=n;i++)
   scanf("%d",&c[i][1]);
  for(int i=1;i<=n;i++)
   scanf("%d",&c[i][2]);
  for(int i=1;i<=n;i++)
   scanf("%lf",&w[i]);
  memset(d,0x3f,sizeof(d));
  for(int i=1;i<=v;i++)
   d[i][i]=0;
  for(int i=1;i<=e;i++)
  {
    int x,y,z;
    scanf("%d%d%d",&x,&y,&z);
    d[y][x]=d[x][y]=MIN(d[x][y],z);
  }
  for(int k=1;k<=v;k++)
   for(int i=1;i<=v;i++)
    for(int j=1;j<=v;j++)
     d[i][j]=MIN(d[i][j],d[i][k]+d[k][j]);
  for(int i=0;i<N;i++)
   for(int j=0;j<N;j++)
    for(int k=0;k<5;k++)
     g[i][j][k]=2000000000.00;
  f(1,0,0)=0;
  if(m)f(1,1,1)=0;
  for(int i=2;i<=n;i++)
  {
   f(i,0,0)=f(i-1,0,0)+d[c[i-1][1]][c[i][1]];
   for(int j=1;j<=m;j++)
   {
     f(i,j,0)=Min(f(i-1,j,0)+d[c[i-1][1]][c[i][1]],f(i-1,j,1)+w[i-1]*d[c[i-1][2]][c[i][1]]+(1.0-w[i-1])*d[c[i-1][1]][c[i][1]]);
     f(i,j,1)=f(i-1,j-1,1)+w[i]*w[i-1]*d[c[i-1][2]][c[i][2]]+(1.0-w[i])*w[i-1]*d[c[i-1][2]][c[i][1]]+(1.0-w[i])*(1.0-w[i-1])*d[c[i-1][1]][c[i][1]]+w[i]*(1.0-w[i-1])*d[c[i-1][1]][c[i][2]];
     f(i,j,1)=Min(f(i,j,1),f(i-1,j-1,0)+w[i]*d[c[i-1][1]][c[i][2]]+(1.0-w[i])*d[c[i-1][1]][c[i][1]]);
   }
  }
  D ans=2000000000.00;
  for(int i=0;i<=m;i++)
   ans=Min(ans,Min(f(n,i,1),f(n,i,0)));
  printf("%.2lf",ans);
  return 0;
}