Nordic Collegiate Programming Contest 2020 D.Damsindistress (dp)

简介: Nordic Collegiate Programming Contest 2020 D.Damsindistress (dp)

linkkkkk

题意:

给定每个大坝先有水量以及总容量,超过总容量时就会流向下一级(靠近根)的大坝。问最少需要多少新的水可以使整个大坝体系的根崩溃?只能往一个里面加水。

代码:

啊开始的d p状态想错了,但还是记录一下,假设d p [ i ]表示从i加水使得水量能够淹没0的水量,转移就要么从自身加水,要么从子节点转移。但是这样又要维护路径上的水量和。

换一个思路,d p [ i ]表示要淹没第i个大坝所需的水量,对于转移:

首先,他自己的代价是c i − u i

然后,父节点要淹没的水量是d p [ f a [ i ] ],再减去自身水量c i就是让父节点也淹没的代价。

由于输入编号是有序的,即某个节点的父节点一定在这个节点之前,所以直接从前向后扫一遍。

还有个看不懂的思路:点击跳转

代码:

const int maxn=2e5+7,inf=0x3f3f3f3f;
int fa[maxn],dp[maxn],n,c[maxn],u[maxn];
int main(){
    n=read,dp[0]=read,c[0]=dp[0];
    rep(i,1,n){
        fa[i]=read,c[i]=read,u[i]=read;
    }
    rep(i,1,n){
        dp[i]=c[i]-u[i]+max(0,dp[fa[i]]-c[i]);
    }
    int ans=inf;
    rep(i,0,n) ans=min(ans,dp[i]);
    write(ans);
    return 0;
}
/**/
目录
相关文章
German Collegiate Programming Contest 2019 B . Bouldering (最短路)
German Collegiate Programming Contest 2019 B . Bouldering (最短路)
99 0
German Collegiate Programming Contest 2019 B . Bouldering (最短路)
|
人工智能
atcoder AtCoder Beginner Contest 210 D - National Railway(dp)
atcoder AtCoder Beginner Contest 210 D - National Railway(dp)
114 0
The 15th Chinese Northeast Collegiate Programming Contest C. Vertex Deletion(树形dp)
The 15th Chinese Northeast Collegiate Programming Contest C. Vertex Deletion(树形dp)
110 0
|
机器学习/深度学习 人工智能 BI
The 15th Chinese Northeast Collegiate Programming Contest
The 15th Chinese Northeast Collegiate Programming Contest
142 0
|
机器学习/深度学习 人工智能 Java
AtCoder Beginner Contest 215 D - Coprime 2 (质因子分解 gcd)
AtCoder Beginner Contest 215 D - Coprime 2 (质因子分解 gcd)
102 0
AtCoder Beginner Contest 214 F - Substrings(subsequence DP)
AtCoder Beginner Contest 214 F - Substrings(subsequence DP)
95 0
|
定位技术
German collegiate programming contest 2012 - Ski Jumping
首先用动能定理算出平抛的初速度v0,然后分三种情况,0~L/2,L/2~L,L~无穷远。
135 0
German collegiate programming contest 2012 - Ski Jumping