AcWing 233. 换教室
原题链接
中等
作者:
AkTtt
,
2023-10-10 18:32:49
,
所有人可见
,
阅读 70
换教室
(果然期望dp一看题解就会,自己一写就废)
C++ 代码
#include <iostream>
#include <algorithm>
#include <functional>
#include <stack>
#include <vector>
#include <iomanip>
#include <queue>
#include <cstring>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e3 + 10;
const int INF = 0x3f3f3f3f,mod = 998244353;
const LL INFF = 0x3f3f3f3f3f3f3f3f;
int t, n, q, v, m;
int c[N], d[N], g[N][N];
double p[N], f[N][N][2];
void flody(){
for(int k = 1; k <= 300; k++){
for(int i = 1; i <= 300; i++){
for(int j = 1; j <= 300; j++){
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
}
}
}
void solve()
{
cin >> n >> q >> v >> m;
for(int i = 1; i <= n; i++)cin >> c[i];
for(int i = 1; i <= n; i++)cin >> d[i];
for(int i = 1; i <= n; i++)cin >> p[i];
for(int i = 1; i <= 300; i++){
for(int j = 1; j <= 300; j++){
if(i != j)g[i][j] = INF;
}
}
while(m--){
int a, b, c;
cin >> a >> b >> c;
g[a][b] = min(g[a][b], c);
g[b][a] = min(g[b][a], c);
}
flody();
for(int i = 0; i <= n; i++)
for(int j = 0; j <= q; j++)
for(int k = 0; k <= 1; k++)
f[i][j][k] = INF;
f[1][1][1] = 0;
f[1][0][0] = 0;
for(int i = 2; i <= n; i++){
for(int j = 0; j <= min(q, i); j++){
double case1 = f[i - 1][j][0] + g[c[i - 1]][c[i]];
double case2 = f[i - 1][j][1] + g[c[i - 1]][c[i]] * (1 - p[i - 1]) + g[d[i - 1]][c[i]] * p[i - 1];
f[i][j][0] = min(case1, case2);
if(j > 0){
double case3 = f[i - 1][j - 1][0] + g[c[i - 1]][c[i]] * (1 - p[i]) + g[c[i - 1]][d[i]] * p[i];
double case4 = f[i - 1][j - 1][1] + g[c[i - 1]][c[i]] * (1 - p[i]) * (1 - p[i - 1]) + g[c[i - 1]][d[i]] * (1 - p[i - 1]) * p[i]
+ g[d[i - 1]][c[i]] * p[i - 1] * (1 - p[i]) + g[d[i - 1]][d[i]] * p[i] * p[i - 1];
//f[i-1][j-1][1]+g[c[i-1]][c[i]]*(1-p[i-1])*(1-p[i])+g[c[i-1]][d[i]]*(1-p[i-1])*p[i]+g[d[i-1]][c[i]]*(1-p[i])*p[i-1]+g[d[i-1]][d[i]]*p[i-1]*p[i];
f[i][j][1] = min(case3, case4);
}
// cout << f[i][j][1] << ' ' << f[i][j][0] << endl;
}
}
double ans = INF;
for(int i = 0; i <= q; i++)ans = min(ans, min(f[n][i][0], f[n][i][1]));
cout << fixed << setprecision(2) << ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// cin>>t;
t=1;
while(t--)
{
solve();
}
}
/*
1.深呼吸,不要紧张,慢慢读题,读明白题,题目往往比你想的简单。
2.暴力枚举:枚举什么,是否可以使用一些技巧加快枚举速度(预处理、前缀和、数据结构、数论分块)。
3.贪心:需要排序或使用数据结构(pq)吗,这么贪心一定最优吗。
4.二分:满足单调性吗,怎么二分,如何确定二分函数返回值是什么。
5.位运算:按位贪心,还是与位运算本身的性质有关。
6.数学题:和最大公因数、质因子、取模是否有关。
7.dp:怎么设计状态,状态转移方程是什么,初态是什么,使用循环还是记搜转移。
8.搜索:dfs 还是 bfs ,搜索的时候状态是什么,需要记忆化吗。
9.树上问题:是树形dp、树上贪心、或者是在树上搜索。
10.图论:依靠什么样的关系建图,是求环统计结果还是最短路。
11.组合数学:有几种值,每种值如何被组成,容斥关系是什么。
12.交互题:log(n)次如何二分,2*n 次如何通过 n 次求出一些值,再根据剩余次数求答案。
13.如果以上几种都不是,多半是有一个 point 你没有注意到,记住正难则反。
*/