题目
思路
题目中对租教室的描写满足了“差分”，立即想到差分处理每次借教室但是怎么判断还能不能借？只能用前缀和计算当前天数有无教室剩余，但是会TLE咋办？
让我们二分它！！！
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std
;
#define N 2005
const double inf
= 1e20;
int n
,m
,v
,e
;
int c
[N
],d
[N
];
double k
[N
],f
[N
][N
][2],mp
[305][301];
void Readin(){
scanf("%d%d%d%d",&n
,&m
,&v
,&e
);
for(int i
=1; i
<=n
; i
++)
scanf("%d",&c
[i
]);
for(int i
=1; i
<=n
; i
++)
scanf("%d",&d
[i
]);
for(int i
=1; i
<=n
; i
++)
scanf("%lf",&k
[i
]);
for(int i
=1; i
<=v
; i
++)
for(int j
=1; j
<=v
; j
++)
mp
[i
][j
] = mp
[j
][i
] = inf
;
int a
,b
;double w
;
for(int i
=1; i
<=e
; i
++){
scanf("%d%d%lf",&a
,&b
,&w
);
mp
[a
][b
] = mp
[b
][a
] = min(mp
[a
][b
],w
);
}
return;
}
void floyed(){
for(int k
=1; k
<=v
; k
++)
for(int i
=1; i
<=v
; i
++)
for(int j
=1; j
<=v
; j
++)
if(k
!=i
&& i
!=j
&& j
!=k
)
mp
[i
][j
] = min(mp
[i
][j
],mp
[i
][k
]+mp
[k
][j
]);
return;
}
int main()
{
Readin();
floyed();
for(int i
=1; i
<=v
; i
++)
mp
[i
][i
] = mp
[i
][0] = mp
[0][i
] = 0;
for(int i
=0 ; i
<=n
; i
++)
for(int j
=0; j
<=m
; j
++)
f
[i
][j
][0] = f
[i
][j
][1] = inf
;
f
[1][0][0] = f
[1][1][1] = 0;
for(int i
=2; i
<=n
; i
++){
f
[i
][0][0] = f
[i
-1][0][0]+mp
[c
[i
-1]][c
[i
]];
for(int j
=1; j
<=min(i
,m
); j
++){
int a1
= c
[i
],a2
= d
[i
],b1
= c
[i
-1],b2
= d
[i
-1];
f
[i
][j
][0] = min(f
[i
][j
][0],f
[i
-1][j
][0]+mp
[a1
][b1
]);
f
[i
][j
][0] = min(f
[i
][j
][0],f
[i
-1][j
][1]+mp
[a1
][b2
]*k
[i
-1]+mp
[a1
][b1
]*(1-k
[i
-1]));
f
[i
][j
][1] = min(f
[i
][j
][1],f
[i
-1][j
-1][0]+mp
[a2
][b1
]*k
[i
]+mp
[a1
][b1
]*(1-k
[i
]));
double cmp
= mp
[a1
][b1
]*(1-k
[i
])*(1-k
[i
-1])+mp
[a2
][b2
]*k
[i
]*k
[i
-1]+mp
[a1
][b2
]*(1-k
[i
])*k
[i
-1]+mp
[a2
][b1
]*k
[i
]*(1-k
[i
-1]);
f
[i
][j
][1] = min(f
[i
][j
][1],f
[i
-1][j
-1][1]+cmp
);
}
}
for(int i
=0; i
<=m
; i
++)
f
[0][0][0] = min(f
[0][0][0],min(f
[n
][i
][0],f
[n
][i
][1]));
printf("%.02lf",f
[0][0][0]);
return 0;
}
