# 斯德哥尔摩 的博客

### P1850 换教室

posted on 2018-10-29 21:12:39 | under 刷题 |

P1850 换教室

$$dp[i][j][0]=\min\left\{\begin{array}{}dp[i-1][j][0]+path[c_{i-1}][c_i],\\\\dp[i-1][j][1]+path[c_{i-1}][c_i]\times(1-k_{i-1})\\+path[d_{i-1}][c_i]\times k_{i-1}\end{array}\right.$$

$$dp[i][j][1]=\min\left\{\begin{array}{}dp[i-1][j-1][0]+path[c_{i-1}][c_i]\times(1-k_i)\\+path[c_{i-1}][d_i]\times k_i\\\\dp[i-1][j-1][1]+path[d_{i-1}][d_i]\times k_{i-1}\times k_i\\+path[d_{i-1}][c_i]\times k_{i-1}\times(1-k_i)\\+path[c_{i-1}][d_i]\times(1-k_{i-1})\times k_i\\+path[c_{i-1}][c_i]\times(1-k_{i-1})\times(1-k_i)\end{array}\right.$$

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 2010
#define MAXM 310
#define MAX 999999999
using namespace std;
int n,m,V,E,c=1;
int path[MAXM][MAXM];
double ans=(1LL<<62),dp[MAXN][MAXN][2];
struct Time{
int c,d;
double k;
}a[MAXN];
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void floyd(){
for(int k=1;k<=V;k++)
for(int i=1;i<=V;i++)
for(int j=1;j<=V;j++)
path[i][j]=min(path[i][j],path[i][k]+path[k][j]);
}
void work(){
int x1,x2,y1,y2;
double w1,w2,w3,w4;
dp[1][0][0]=dp[1][1][1]=0;
for(int i=2;i<=n;i++){
x1=a[i-1].c;y1=a[i-1].d;x2=a[i].c;y2=a[i].d;

w1=path[x1][x2];w2=path[x1][y2];w3=path[y1][x2];w4=path[y1][y2];

dp[i][0][0]=dp[i-1][0][0]+w1;
for(int j=1;j<=i&&j<=m;j++){

dp[i][j][0]=min(dp[i][j][0],
min(dp[i-1][j][0]+w1,
dp[i-1][j][1]+w1*(1.00-a[i-1].k)+w3*a[i-1].k
)
);

dp[i][j][1]=min(dp[i][j][1],
min(dp[i-1][j-1][0]+w1*(1.00-a[i].k)+w2*a[i].k,
dp[i-1][j-1][1]+
w4*a[i-1].k*a[i].k+w3*a[i-1].k*(1.00-a[i].k)+
w2*(1.00-a[i-1].k)*a[i].k+w1*(1.00-a[i-1].k)*(1.00-a[i].k)
)
);
}
}
for(int i=0;i<=m;i++)ans=min(ans,min(dp[n][i][0],dp[n][i][1]));
printf("%.2lf\n",ans);
}
void init(){
int u,v,w;
for(int i=1;i<=n;i++)scanf("%lf",&a[i].k);
for(int i=1;i<=V;i++)
for(int j=1;j<=V;j++)
path[i][j]=(i==j?0:MAX);
for(int i=1;i<=E;i++){