$dp$。

這道題最關鍵的是這句話：

跳出思維局限大膽設狀態，設$f_{x, i, j}$表示從$x$到根要經過$i$條公路，$j$條鐵路的代價，那么對于一個葉子結點，有$f_{x, i, j} = c_x * (a_x + i) * (b_x + j)$，對于內部結點，有轉移：

　　$f_{x, i, j} = min(f_{lson(x), i + 1, j} + f_{rson(x), i, j}, f_{lson(x), i, j}) + f_{rson(x), i, j + 1}$。

然后$40000 * 40 * 40$就快$512MB$了，然后最后一個點就光榮$MLE$了。

所以要寫成記搜的，就可以省掉一半$f$數組的空間。

時間復雜度上界是$O(n * 40 * 40)$。

Code：

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;const int N = 20001;
const int M = 41;
const ll inf = 0x3f3f3f3f3f3f3f3f;int n, son[N][2], a[N], b[N], c[N];
ll f[N][M][M];template <typename T>
inline void read(T &X) {X = 0; char ch = 0; T op = 1;for(; ch > '9'|| ch < '0'; ch = getchar())if(ch == '-') op = -1;for(; ch >= '0' && ch <= '9'; ch = getchar())X = (X << 3) + (X << 1) + ch - 48;X *= op;
}template <typename T>
inline T min(T x, T y) {return x > y ? y : x;
}   ll dfs(int x, int i, int j) {if(x >= n) return 1LL * c[x - n + 1] * (a[x - n + 1] + i) * (b[x - n + 1] + j);if(f[x][i][j] != inf) return f[x][i][j];return f[x][i][j] = min(dfs(son[x][0], i + 1, j) + dfs(son[x][1], i, j), dfs(son[x][0], i, j) + dfs(son[x][1], i, j + 1));
}int main() {
//    freopen("road20.in", "r", stdin);
    read(n);for(int lc, rc, i = 1; i < n; i++) {read(lc), read(rc);if(lc < 0) lc = n - 1 - lc;if(rc < 0) rc = n - 1 - rc;son[i][0] = lc, son[i][1] = rc;}for(int i = 1; i <= n; i++) read(a[i]), read(b[i]), read(c[i]);memset(f, 0x3f, sizeof(f));printf("%lld\n", dfs(1, 0, 0));return 0;
}

View Code

?

轉載于:https://www.cnblogs.com/CzxingcHen/p/9908060.html

總結

以上是生活随笔為你收集整理的Luogu 4438 [HNOI/AHOI2018]道路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。