1 条题解
-
-1
#include <bits/stdc++.h> #define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout) #define ALL(x) x.begin(), x.end() #define mset(a, b) memset(a, b, sizeof a) #define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) #define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--) using namespace std; template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;} template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;} typedef long long ll; typedef double db; const int N = 65; template<int N, int M, class T> struct Link { #define erep(k, G, o) for(int k(G.HEAD[o]); k; k = G.NXT[k]) int HEAD[N], NXT[M], tot; T W[M]; void clear() {mset(HEAD, 0); tot = 0;} void add(int x, T w) {NXT[++tot] = HEAD[x]; W[HEAD[x] = tot] = w;} T& operator[] (int k) {return W[k];} }; Link<N, N * 2, int> G; int s[N]; db c[N], k; db dp[N][N][N], tmp[N][N]; db pw[N]; void dfs(int o, int m, int dep) { rep(i, 0, m) rep(d, 0, dep) dp[o][i][d] = c[o] * pw[d]; erep(k, G, o) { int v = G[k]; dfs(v, m, dep + 1); mset(tmp, 0); rep(i, 0, m) rep(j, 0, m - i) rep(d, 0, dep) { tomax(tmp[i + j][d], dp[o][i][d] + dp[v][j][d + 1]); if(j > 0) tomax(tmp[i + j][d], dp[o][i][d] + dp[v][j - 1][1]); } rep(i, 0, m) rep(d, 0, dep) dp[o][i][d] = tmp[i][d]; } } db calc(int m) { dfs(1, m, 0); return dp[1][m][0]; } int main() { File(trans); int n, m; scanf("%d%d%lf", &n, &m, &k); pw[0] = 1.0; rep(i, 1, n) pw[i] = pw[i - 1] * k; rep(i, 1, n) scanf("%d", &s[i]); rep(i, 1, n) scanf("%lf", &c[i]); db ans = 0; for(int d = 2, p = s[1]; p != 1; d++, p = s[p]) { G.clear(); int t = s[p]; s[p] = 1; rep(i, 2, n) G.add(s[i], i); tomax(ans, calc(m - (t != s[p])) / (1 - pw[d])); s[p] = t; } printf("%.2lf\n", ans); return 0; }
- 1
信息
- ID
- 1065
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 12
- 已通过
- 3
- 上传者