Qiuly

「NOI2008」奥运物流 基环树+DP luoguP4202
不知道为什么啊远古时期的出题人这么喜欢把 $\rm{DP}$ 往基环树上套。和迷失游乐园那题一样,首先还是考虑树的...
扫描右侧二维码阅读全文
22
2019/10

「NOI2008」奥运物流 基环树+DP luoguP4202

不知道为什么啊远古时期的出题人这么喜欢把 $\rm{DP}$ 往基环树上套。

和迷失游乐园那题一样,首先还是考虑树的情况。

可以发现答案为 $\sum_{i=1}^{n}C_iK^{dep_{i}}$ ,然后对于每一次修改,显然要使答案更大,就需要使得 $dep$ 更小,这意味着每一次修改一定是将某一个点的后继修改为 $1$ 。

接下来的部分考虑 $\rm{DP}$ ,设 $dp_{i,j}$ 表示在 $i$ 的子树中有 $j$ 个点的后继修改成了 $1$ 时 $R(i)$ 的最大值。

但是转移不好转移,毕竟我们可能将 $i$ 的后继放到上面去了,也就是说 $i$ 的深度是一直在变化的,这导致我们没办法得到 $i$ 的深度。

新增一维状态 $k$ 表示 $i$ 当前的深度即可。转移的时候分两种情况:

​ $1.$ 将 $i$ 的后继修改为 $1$ :

$$ dp_{u,i,1}=C_u\times K+\sum \max(dp_{v,j,1},dp_{v,j,2}) $$

​ $2.$ 没有修改 $i$ 的后继。

$$ dp_{u,i,k}=C_u\times K^k+\sum \max(dp_{v,j,1},dp_{v,j,k+1}) $$

然后对于环的情况,只需要考虑断掉哪条边,留下一个一定长度的环,或者说直接枚举将环上的哪个点的后继修改为 $1$ ,然后依次计算答案即可。

*转移的时候,可以令 $g_{v,i,k}=\max(dp_{v,j,1},dp_{v,j,k+1})$ ,然后背包即可。

*修改了的转移:

memset(res,0,sizeof(res));
for(int to=2;to<=n;++to) 
    if(suc[to]==u)
        for(int j=m;j>=0;--j)
            for(int l=j;l>=0;--l) 
                res[j]=max(res[j],res[l]+g[to][j-l][1]);
for(int i=1;i<=m;++i) f[u][i][1]=C[u]*K+res[i-1];

*不修改的转移:

memset(res,0,sizeof(res));
for(int to=2;to<=n;++to) 
    if(suc[to]==u)
        for(int j=m;j>=0;--j)
            for(int l=j;l>=0;--l) 
                res[j]=max(res[j],res[l]+g[to][j-l][k]);
for(int i=0;i<=m;++i) f[u][i][k]=C[u]*mul[k]+res[i];

注意一下细节,尤其是修改后 $i$ 的修改也要在"修改次数"计算。

#if By_Qiuly
We're here to put a dent in the universe. Otherwise why else even be here?
(FAKE)solution(baoli) : 
algorithm : 
#endif

#include <vector>
#include <cstdio>
#include <string>   
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
#define FILE(name) freopen(name".in","r",stdin),freopen(name".out","w",stdout)

const int N=65;
int n,m,suc[N];
double ans,K,C[N],res[N],f[N][N][N],g[N][N][N],mul[N];

namespace Function {
    template <typename T> inline void chkmax(T&x,T y) {x=x>y?x:y;}
    template <typename T> inline void chkmin(T&x,T y) {x=x<y?x:y;}
    template <typename T> inline void IN(T&x) {
        char ch;bool flag=0;x=0;
        while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
        while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
        if(flag) x=-x;
    }
}using namespace Function;

inline void solve(int u,int dep) {
    for(int to=2;to<=n;++to) if(suc[to]==u) solve(to,dep+1);
    for(int k=min(2,dep);k<=dep;++k) {
        memset(res,0,sizeof(res));
        for(int to=2;to<=n;++to) 
            if(suc[to]==u)
                for(int j=m;j>=0;--j)
                    for(int l=j;l>=0;--l) 
                        res[j]=max(res[j],res[l]+g[to][j-l][k]);
        for(int i=0;i<=m;++i) f[u][i][k]=C[u]*mul[k]+res[i];
    }
    if(dep>1) {
        memset(res,0,sizeof(res));
        for(int to=2;to<=n;++to) 
            if(suc[to]==u)
                for(int j=m;j>=0;--j)
                    for(int l=j;l>=0;--l) 
                        res[j]=max(res[j],res[l]+g[to][j-l][1]);
        for(int i=1;i<=m;++i) f[u][i][1]=C[u]*K+res[i-1];
    }
    for(int i=0;i<=m;++i)
        for(int k=0;k<dep;++k)
            g[u][i][k]=max(f[u][i][1],f[u][i][k+1]);
}

int main() {
    // FILE("P4202");
    freopen("P4202.in","r",stdin);
    IN(n),IN(m),scanf("%lf",&K);
    for(int i=1;i<=n;++i) IN(suc[i]);
    for(int i=1;i<=n;++i) scanf("%lf",&C[i]);
    mul[0]=1.0;
    for(int i=1;i<=n;++i) mul[i]=mul[i-1]*K;
    for(int now=suc[1],len=2;now!=1;now=suc[now],++len) {
        int last=suc[now];suc[now]=1;
        memset(f,0,sizeof(f)),
        memset(g,0,sizeof(g));
        for(int tmp=1;tmp<=n;++tmp) 
            if(suc[tmp]==1) solve(tmp,1);
        memset(res,0,sizeof(res));
        for(int tmp=1;tmp<=n;++tmp) 
            if(suc[tmp]==1)
                for(int j=m;j>=0;--j)
                    for(int k=j;k>=0;--k) 
                        res[j]=max(res[j],res[k]+f[tmp][j-k][1]);
        double tmp=(last==1)?res[m]:0.0;
        for(int i=0;i<m;++i) tmp=max(tmp,res[i]);
        ans=max(ans,(tmp+C[1])/(1.0-mul[len])),suc[now]=last;
    }
    printf("%.2lf\n",ans);
    return 0;
}
最后修改:2019 年 10 月 22 日 08 : 45 PM

发表评论