1 条题解

  • -1
    @ 2022-8-29 9:20:23
    #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
    上传者