Luogu

算法

这是一道树形DP。

设 $f[i] [j]$ 表示当前节点为 $i$ 用掉 $j$ 秒所取得的最大值。

那么当这条走廊通向叶子节点 $i$时：

if (i是叶子节点) f[i][j]=max(i的画数,(j-该走廊通过时间)/5);

否则枚举左子树时间，分配给左右子树取和的最大值：

for (re int k=0;k<=time-tree[now].time;k++)
    f[now][time]=max(f[now][time],Dfs(now<<1,k)+Dfs(now<<1|1,time-tree[now].time-k));

直接记搜即可。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;
inline int read() //读优
{
    int X=0,w=1; char ch=getchar();
    while (ch<'0'||ch>'9') { if (ch=='-') w=-1; ch=getchar(); }
    while (ch>='0'&&ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
    return X*w;
}
struct node //树节点
{
    int time,sum;
    node() { this->time=this->sum=0; }
}tree[10010];
int n,cnt=0;
inline void build(int now) //建树，说明见上
{
    tree[now].time=read()*2; tree[now].sum=read();
    if (tree[now].sum!=0) return;
    else { build(now<<1); build(now<<1|1); }
}
int f[1010][1010]; //f[i][j]表示当前节点为i用掉j秒所取得的最大值
inline int Dfs(int now,int time) //now表示当前节点，time表示剩余时间
{
    if (f[now][time]||!time) return f[now][time]; //记搜边界，计算过或没时间了
    if (tree[now].sum) { f[now][time]=min(tree[now].sum,(time-tree[now].time)/5); return f[now][time]; }
    //叶子节点处理
    for (re int k=0;k<=time-tree[now].time;k++) //枚举一下左子树的时间，分别计算左右子树，再加起来取max
        f[now][time]=max(f[now][time],Dfs(now<<1,k)+Dfs(now<<1|1,time-tree[now].time-k));
    return f[now][time]; //返回
}
int main()
{
    n=read()-1; //注意这里要-1
    build(1); //建树
    printf("%d\n",Dfs(1,n)); //直接Dfs输出
    return 0;
}