当前位置：首页 > news >正文

Eating Everything Efficiently（树形DP+思维）

news 来源：原创 2024/5/3 23:21:56

传送门

1.题目大意：给出一个有向无环带权图，现在从0号节点进入，每到一个节点都可以选或者不选，如果选并且这是选择的第 $i$ 个节点，那么产生的贡献是 ${\frac{w_i}{2^{i-1}}}$ ，求最大贡献

2.虽然这是一个图的问题，但是有向图也可以看做有根树，我们直接dfs即可。然后我们发现在这个问题中如果考虑从前向后转移，是一件很麻烦的事情，因为每个节点都可能选或不选，这样对后面节点的影响是未知的。因此我们可以这样想，不用上面的计算公式，如果当前节点选，那么相当于后面选的节点都除以二，这个过程我们可以在dfs回溯的时候完成，即每次先让 $d [u]$ 保存其所有子节点的最大值，然后状态转移：

$d [u] = m a x (d [u], d [u] / 2.0 + a [u])$

那么最后的答案就是对每个阶段的答案取 $m a x$

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <bitset>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=5e5+10;

vector<int> G[maxn];
double a[maxn],d[maxn];
int n,m;
double ans;

void dfs(int u){
    if(d[u]) return;
    d[u]=0.0;
    for(auto v: G[u]){
        dfs(v);
        d[u]=max(d[u],d[v]);
    }
    d[u]=max(d[u],d[u]/2.0+a[u]);
    ans=max(ans,d[u]);
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lf",&a[i]);
    for(int i=1,u,v;i<=m;i++){
        scanf("%d%d",&u,&v);
        u++,v++;
        G[u].push_back(v);
    }
    dfs(1);
    printf("%.6f",ans);
    return 0;
}