luogu1850 [NOIp2016]换教室 (floyd+dp)

首先floyd求出每两点间的距离（注意自己到自己的距离要设成0）

然后就是dp了

一开始照着Lifeguards的样子，钦定了一下i这个点一定要选，然后发现复杂度不对，还想了好长时间优化

然后一翻题解，直接两种状态选或不选分开算O(1)转移多好（所以年轻人不要整天满脑子都是钦定钦定的）

但为什么Lifeguards要钦定呢？因为如果你有一个删掉的状态，那我无法确定前面的到底到哪是没删的

那就是$f[i][j][1/0]=max(f[i][j][1/0]+....)$，f[i][j][0/1]是换到第i个、换了j个、i号没换/换了的最小值

....的内容大概就是这几种状态间转移的期望，讨论讨论就行了

 #include<bits/stdc++.h>

 #define pa pair<int,int>

 #define lowb(x) ((x)&(-(x)))

 #define REP(i,n0,n) for(i=n0;i<=n;i++)

 #define PER(i,n0,n) for(i=n;i>=n0;i--)

 #define MAX(a,b) ((a>b)?a:b)

 #define MIN(a,b) ((a<b)?a:b)

 #define CLR(a,x) memset(a,x,sizeof(a))

 #define rei register int

 using namespace std;

 typedef long long ll;

 const int maxn=,maxm=,maxv=;

 inline ll rd(){

     ll x=;char c=getchar();int neg=;

     while(c<''||c>''){if(c=='-') neg=-;c=getchar();}

     while(c>=''&&c<='') x=x*+c-'',c=getchar();

     return x*neg;

 }

 int N,M,V,E;

 int pos[maxn][],dis[maxn][maxn];

 int sum[maxn];

 double f[maxn][maxn][],c[maxn];

 void floyd(){

     for(int i=;i<=V;i++) dis[i][i]=;

     for(int i=;i<=V;i++){

         for(int j=;j<=V;j++){

             for(int k=;k<=V;k++){

                 if(dis[j][i]>=1e9||dis[i][k]>=1e9) continue;

                 dis[j][k]=min(dis[j][i]+dis[i][k],dis[j][k]);

             }

         }

     }

 }

 int main(){

     //freopen(".in","r",stdin);

     int i,j,k;

     N=rd(),M=rd(),V=rd(),E=rd();

     if(N==){printf("0.00\n");return ;}

     for(i=;i<=N;i++) pos[i][]=rd();

     for(i=;i<=N;i++) pos[i][]=rd();

     for(i=;i<=N;i++) scanf("%lf",&c[i]);

     memset(dis,,sizeof(dis));

     for(i=;i<=E;i++){

         int a=rd(),b=rd(),c=rd();

         dis[a][b]=min(dis[a][b],c);

         dis[b][a]=min(dis[b][a],c);

     }floyd();

     for(i=;i<=N;i++) for(j=;j<=M;j++) f[i][j][]=f[i][j][]=1e9;

     f[][][]=f[][][]=f[][][]=;

     for(i=;i<=N;i++){

         for(j=;j<=min(i,M);j++){

             f[i][j][]=min(f[i-][j][]+dis[pos[i-][]][pos[i][]],

                            f[i-][j][]+dis[pos[i-][]][pos[i][]]*(-c[i-])+dis[pos[i-][]][pos[i][]]*c[i-]);

             if(j){

                 f[i][j][]=min(f[i-][j-][]+dis[pos[i-][]][pos[i][]]*(-c[i])+dis[pos[i-][]][pos[i][]]*c[i],

                                f[i-][j-][]+(dis[pos[i-][]][pos[i][]]*(-c[i])+dis[pos[i-][]][pos[i][]]*c[i])*(-c[i-])+

                                               (dis[pos[i-][]][pos[i][]]*(-c[i])+dis[pos[i-][]][pos[i][]]*c[i])*c[i-]);

             }

         }

     }

     double ans=1e9;

     for(i=;i<=M;i++) ans=min(ans,min(f[N][i][],f[N][i][]));

     printf("%.2lf\n",ans);

     return ;

 }