正文

[树形dp]jzoj5788餐馆(代码片段)

mastervan  mastervan  2022-12-21  556

关键词：

Description

K妹的胡椒粉大卖，这辣味让食客们感到刺激，许多餐馆也买这位K妹的账。有N家餐馆，有N-1条道路，这N家餐馆能相互到达。K妹从1号餐馆开始。每一个单位时间，K妹可以在所在餐馆卖完尽量多的胡椒粉，或者移动到有道路直接相连的隔壁餐馆。第i家餐馆最多需要A[i]瓶胡椒粉。K妹有M个单位的时间，问她最多能卖多少胡椒粉。

Input

第一行有两个正整数N，M。
第二行描述餐馆对胡椒粉的最大需求量，有N个正整数，表示A[i]。
接下来有N-1行描述道路的情况，每行两个正整数u，v，描述这条道路连接的两个餐馆。

Output

一个整数，表示她最多能卖的胡椒粉瓶数。

Sample Input

Sample Output

样例1输出
14

样例2输出
3

样例3输出
15

Data Constraint

对于10%的数据，N≤20。
对于50%的数据，N≤110。
对于100%的数据1 ≤ N, M ≤ 500，1 ≤ A[i]≤ 10^6，
第5到第10个测试点都有多个子测试。

Hint

在样例1的中，辣妹到达城市2后就恰好没时间卖辣椒粉了。

分析

这题比赛时并没有想做，因为折返的骚操作让我想不到怎么搞方程（其实一开始列的方程还是挺像正解的233）

设f[i][j][0/1]表示以i为根的子树用了j的单位时间有/无到达根的最大收益，方程显然：

f[u][j][1]+f[v][k][0]→f[u][j+k+1][1]

f[u][j][0]+f[v][k][1]→f[u][j+k+2][1]

f[u][j][0]+f[v][k][0]→f[u][j+k+2][0]

然后这样是O(n²)可以证明，这里不做过多叙述

#include <iostream>
#include <cstdio>
using namespace std;
const int N=501;
struct Edge 
    int u,v,nx;
g[2*N];
int cnt,list[N];
int f[N][N][2];
int a[N],d[N];
int n,m;

void Add(int u,int v) 
    g[++cnt].u=u;g[cnt].v=v;g[cnt].nx=list[u];list[u]=cnt;


void Init() 
    scanf("%d%d",&n,&m);
    for (int i=0;i<n;i++) scanf("%d",&a[i+1]);
    for (int i=0;i<n-1;i++) 
        int u,v;
        scanf("%d%d",&u,&v);
        Add(u,v);Add(v,u);
    


void Dfs(int u,int fa) 
    for (int i=list[u];i;i=g[i].nx)
    if (g[i].v!=fa) 
        Dfs(g[i].v,u);
        for (int j=m;j>=0;j--)
        for (int k=0;k<=m;k++) 
            if (j-k-2<0) break;
            f[u][j][1]=max(f[u][j][1],f[u][j-k-2][1]+f[g[i].v][k][0]);
        
        for (int j=m;j>=0;j--)
        for (int k=0;k<=m;k++) 
            if (j-k-1<0) break;
            f[u][j][1]=max(f[u][j][1],f[u][j-k-1][0]+f[g[i].v][k][1]);
        
        for (int j=m;j>=0;j--)
        for (int k=0;k<=m;k++) 
            if (j-k-2<0) break;
            f[u][j][0]=max(f[u][j][0],f[u][j-k-2][0]+f[g[i].v][k][0]);
        
    
    for (int i=m;i>=1;i--)
    f[u][i][0]=max(f[u][i][0],f[u][i-1][0]+a[u]),
    f[u][i][1]=max(f[u][i][1],f[u][i-1][1]+a[u]);


int main() 
    freopen("dostavljac.in","r",stdin);
    freopen("dostavljac.out","w",stdout);
    Init();
    Dfs(1,0);
    printf("%d",max(f[1][m][0],f[1][m][1]));
    fclose(stdin);fclose(stdout);

View Code

hdu1561themore,thebetter(树形dp)(代码片段)

Themore,TheBetterTimeLimit:6000/2000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):9938 AcceptedSubmission(s):5788ProblemDescript 查看详情

bailian4118开餐馆dp(代码片段)

4118:开餐馆总时间限制:1000ms内存限制:65536kB描述北大信息学院的同学小明毕业之后打算创业开餐馆.现在共有n个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这n个地点排列在同一条直线上。我们用一个整数序列m1,m... 查看详情

jzoj1340状压dp周长(代码片段)

周长题面DescriptionInputOutputSampleInputSampleOutputDataConstraint解题思路Code题面Description小PP喝饮料中了大奖，奖励n块宽度为1的农田，每一块都有自己的长度，小PP可以自己去选择这N块农田的位置，要按如图的方式拼接在... 查看详情

jzoj1003东莞市选2007拦截导弹——dp(代码片段)

题目：https://jzoj.net/senior/#main/show/1003只要倒推一下第一次上升的最长和第一次下降的最长就行了。不用n^2logn，枚举了j还要用树状数组找值比自己大的元素。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>... 查看详情

[dp]jzoj5907轻功(代码片段)

Description题目背景：尊者神高达进入了基三的世界，作为一个mmorpg做任务是必不可少的，然而跑地图却令人十分不爽。好在基三可以使用轻功，但是尊者神高达有些手残，他决定用梅花桩练习轻功。题目描述：一共有n个木桩，要... 查看详情

jzoj1667(bzoj1801)[ahoi2009]中国象棋——dp(代码片段)

...行有0/1/2个炮，转移即可；注意取模！小心在某处爆int。代码如下：#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>us 查看详情

[dp][二分]jzoj3463军训(代码片段)

DescriptionHYSBZ开学了！今年HYSBZ有n个男生来上学，学号为1…n，每个学生都必须参加军训。在这种比较堕落的学校里，每个男生都会有Gi个女朋友，而且每个人都会有一个欠扁值Hi。学校为了保证军训时教官不会因为学生们都是人... 查看详情

[单调队列优化dp]jzoj3128跳格子(代码片段)

Description奶牛们正在回味童年，玩一个类似跳格子的游戏，在这个游戏里，奶牛们在草地上画了一行N个格子，(3<=N<=250,000)，编号为1..N。就像任何一个好游戏一样，这样的跳格子游戏也有奖励！第i个格子标... 查看详情

[dp][二分]jzoj3467最长上升子序列(代码片段)

Description维护一个序列，使它可以进行下面两种操作：1.在末尾添加一个数字x2.将整个序列变成第x次操作后的样子在每次操作后，输出当前序列的最长上升子序列的长度序列初始时为空 Input输入文件lis.in的第一行有一个正整... 查看详情

[dp总结]树形dp(代码片段)

树形DP树形DP，顾名思义，是在树上进行DP操作，因此往往需要使用DP实现，在转移时，通常先递归求出子树中的解，再在根节点进行计算转移。树中只有两种关系，一种是父子关系，一种是平行关系。下面是几道简单的树形DP。... 查看详情

[dp][博弈][后缀和]jzoj5778没有硝烟的战争(代码片段)

Description被污染的灰灰草原上有羊和狼。有N只动物围成一圈，每只动物是羊或狼。该游戏从其中的一只动物开始，报出[1,K]区间的整数，若上一只动物报出的数是x，下一只动物可以报[x+1,x+K]区间的整数，游戏按顺时针方向进行。... 查看详情

树形dp进阶(代码片段)

树形DP进阶P2899[USACO08JAN]CellPhoneNetworkG考虑结点被谁染色，显然三种情况：自己、父亲、儿子。然后就是裸的树形dpdpdp了。难点在于求dp[u][0]dp[u][0]dp[u][0]，即被儿子染色的情况。我们只需枚举那个儿子被染色即可。voiddf... 查看详情

树形dp入门(代码片段)

今天学了树形dp，发现树形dp就是入门难一些，于是好心的我便立志要发一篇树形dp入门的博客了。树形dp的概念什么的，相信大家都已经明白，这里就不再多说。直接上例题。一、常规树形DPP1352没有上司的舞会题目描述某大学有... 查看详情

jzoj3056noip2012模拟10.27容斥dp数学数字(代码片段)

【NOIP2012模拟10.27】数字Link题面解题思路CodeLinkJzoj【3056】【NOIP2012模拟10.27】数字题面Description一个数字被称为好数字当他满足下列条件：它有2*n个数位，n是正整数(允许有前导0)构成它的每个数字都在给定的数字集合S中。... 查看详情

jzoj3515noip2013模拟11.6b组二分dp软件公司(代码片段)

【NOIP2013模拟11.6B组】软件公司题面DescriptionInputOutputSampleInputSampleOutput【样例解释】DataConstraint解题思路Code题面Description一家软件开发公司有两个项目，并且这两个项目都由相同数量的m个子项目组成，对于同一个项目，... 查看详情

anniversaryparty(树形dp入门)(代码片段)

Anniversaryparty HDU-1520 Thereisgoingtobeapartytocelebratethe80-thAnniversaryoftheUralStateUniversity.TheUniversityhasahierarchicalstructureofemployees.Itmeansthatthesupervisorrelationforms 查看详情

uva12186：anothercrisis（树形dp）(代码片段)

一道简单的树形DP送给你。 Acoupleofyearsago,anewworldwidecrisisstarted,leavingmanypeoplewitheconomicalproblems.Someworkersofaparticularcompanyaretryingtoaskforanincreaseintheirsalaries.数年以前，人们遭受了世界范围的经济危机。于是查看详情

树形dp(代码片段)

一、P2656采蘑菇#include<cstring>#include<cstdio>#include<algorithm>#include<iostream>#include<cmath>usingnamespacestd;#definemaxn80010#definemaxm300010structEdgeintu,v,w,next 查看详情