“访问”美术馆
树形背包问题。容易将美术馆转化成一棵二叉树，将展厅也视为走廊，每个走廊对应二叉树上一个节点。对于这种读入方式可以采用递归建树。
记 \(t_{cost}\) 为通过这个走廊所需的时间，记 \(t_{val}\) 为可以拿到的最多的画，记 \(dp_{i,j}\) 表示在第 \(i\) 个走廊用时 \(j\) 可以拿到的最多的画。
对于每个叶子节点，即展厅，从 \(1 \sim t_{val}\) 枚举拿画需要的时间 \(tim\)，因此有
\[dp_{now,now_{cost} + tim} = \frac{5}{tim} (\frac{5}{tim} \le now_{val}) \]对于非叶子节点，用花费在左右儿子的时间来转移状态。对于当前可用的时间 \(tim\)，有
\[tim_{now} = now_{cost} + tim_{lson} + tim_{rson} \]因此可以得到转移方程
\[dp_{now,tim} = \max_{ltim,rtim \geq 0} (dp_{lson,ltim} + dp_{rson,rtim}) \]最后的结果为 \(dp_{1,n-1}\)。
需要注意的点有：
·警察到达就算结束，给的 \(n\) 需要减一
·对于每条走廊走过去还要回来，因此耗费的时间要乘二
#include<bits/stdc++.h>
#define int long long
#define MAX 1110
using namespace std;
inline int read()
{
int s=0,w=1;
char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) s=(s<<1)+(s<<3)+(c^48),c=getchar();
return s*w;
}
int n,m;
int x;
struct edge
{
int nex,to;
}e[MAX<<1];
int head[MAX],cnt;
inline void add(int x,int y)
{
e[++cnt].nex=head[x];
head[x]=cnt;
e[cnt].to=y;
return;
}
int dp[MAX][MAX]; //dp_{i,j} 第i个走廊用时j获得的最大量
struct Tree
{
int cost,val;
}t[MAX];
void build(int now)
{
t[now].cost=read(),t[now].val=read();
t[now].cost<<=1;
if(t[now].val) return;
build(now<<1),build(now<<1|1);
}
void dfs(int now)
{
if(t[now].val)
{
for(int tim=0;tim+t[now].cost<=n;++tim)
{
if(tim/5>t[now].val) break;
dp[now][t[now].cost+tim]=tim/5;
}
return;
}
dfs(now<<1);
dfs(now<<1|1);
for(int tim=t[now].cost;tim<=n;++tim)
for(int ltim=0;ltim+t[now].cost<=tim;++ltim)
{
int rtim=tim-ltim-t[now].cost;
dp[now][tim]=max(dp[now][tim],dp[now<<1][ltim]+dp[now<<1|1][rtim]);
}
return;
}
signed main()
{
n=read(); --n;
build(1);
dfs(1);
cout<<dp[1][n];
return (0-0);
}