设 dp[i][j][0] 和 dp[i][j][1] 表示在前 i 个里面换了 j 个的最优方案, 0 表示当前换, 1 表示当前不换
分为以下几种情况讨论:
当前点不换, 上一个不换;
上一个换 (失败 + 成功)
当前点换 (失败 + 成功), 上一个不换;
上一个换 (失败 + 成功)
得出转移方程如下:
初始条件 dp[1][0][0] = dp[1][1][1] = 0
- dp[i-1][j][0] + floyd[c[i-1]][c[i]]
- dp[i-1][j][1] + floyd[d[i-1]][c[i]] * k[i-1] + floyd[c[i-1]][c[i]] * (1 - k[i-1])
- dp[i-1][j-1][0] + floyd[c[i-1]][d[i]] * k[i] + floyd[c[i-1]][c[i]] * (1 - k[i])
- dp[i-1][j-1][1] + floyd[d[i-1]][d[i]] * k[i-1] * k[i] + floyd[d[i-1]][c[i]] * k[i-1] * (1 - k[i]) + floyd[c[i-1]][d[i]] * (1 - k[i-1]) * k[i] + floyd[c[i-1]][c[i]] * (1 - k[i-1]) * (1 - k[i])
最后就是不要忘记 j = 0 的时候是没有 种情况的, 而且 ans 只在 dp[n][ ][ ] 处取, 不要把中间状态也打擂了
- #include <cstdio>
- #include <string>
- #include <cstring>
- const int INF = 0x3f3f3f3f;
- int read() {
- int x = 0; char c = getchar();
- while (!isdigit(c)) c = getchar();
- while (isdigit(c)) {
- x = (x << 3) + (x << 1) + (c ^ 48);
- c = getchar();
- }
- return x;
- }
- double fmin(double x, double y) {
- return y > x ? x : y;
- }
- int c[2005], d[2005];
- double k[2005], dp[2005][2005][2], floyd[305][305];
- int main() {
- int n = read(), m = read(), v = read(), e = read();
- for (register int i = 1; i <= n; ++ i) c[i] = read();
- for (register int i = 1; i <= n; ++ i) d[i] = read();
- for (register int i = 1; i <= n; ++ i) scanf("%lf", &k[i]);
- for (register int i = 1; i < v; ++ i)
- for (register int j = i + 1; j <= v; ++ j)
- floyd[i][j] = floyd[j][i] = INF;
- for (register int i = 1; i <= e; ++ i) {
- int u = read(), v = read(), w = read();
- floyd[u][v] = floyd[v][u] = fmin(floyd[u][v], w);
- }
- for (register int k = 1; k <= v; ++ k)
- for (register int i = 1; i < v; ++ i)
- for (register int j = i + 1; j <= v; ++ j)
- if (floyd[i][j] > floyd[i][k] + floyd[k][j])
- floyd[i][j] = floyd[j][i] = floyd[i][k] + floyd[k][j];
- for (register int i = 1; i <= n; ++ i)
- for (register int j = 0; j <= m; ++ j)
- dp[i][j][0] = dp[i][j][1] = INF;
- dp[1][0][0] = dp[1][1][1] = 0;
- for (register int i = 2; i <= n; ++ i) {
- for (register int j = 0; j <= m && j <= i; ++ j) {
- dp[i][j][0] = fmin(dp[i-1][j][0] + floyd[c[i-1]][c[i]],
- dp[i-1][j][1] + floyd[d[i-1]][c[i]] * k[i-1]
- + floyd[c[i-1]][c[i]] * (1 - k[i-1]));
- if (j == 0) continue;
- dp[i][j][1] = fmin(dp[i-1][j-1][0] + floyd[c[i-1]][d[i]] * k[i]
- + floyd[c[i-1]][c[i]] * (1 - k[i]),
- dp[i-1][j-1][1] + floyd[d[i-1]][d[i]] * k[i-1] * k[i]
- + floyd[d[i-1]][c[i]] * k[i-1] * (1 - k[i])
- + floyd[c[i-1]][d[i]] * (1 - k[i-1]) * k[i]
- + floyd[c[i-1]][c[i]] * (1 - k[i-1]) * (1 - k[i]));
- }
- }
- double ans = INF;
- for (register int i = 0; i <= m; ++ i)
- ans = fmin(ans, fmin(dp[n][i][0], dp[n][i][1]));
- printf("%.2lf\n", ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2509332.html