时间戳

首页 > 技术文章 > P1270 “访问”美术馆

P1270 “访问”美术馆

luckyblock 2020-07-07 21:45 原文

知识点: 树形DP

原题面

最近做蓝题有点太顺手了吧（
以后不能在这上面花太多时间了。

分析题意

先扒茬扒茬性质：

  1. 到达一个房间的路径只有一条，显然屋子呈一树形结构，且只有到达叶节点才有贡献。
  2. 没有给出具体房间个数，但总时间 \(T \le 600s\)，可知节点数较少。
  3. 在警察赶来之前 逃走，则花费时间 \(< T\)

先 dfs 建树，考虑树形 DP。

令 \(f_{u,i}\) 表示，在根节点为 \(u\) 的子树中，取得 \(i\) 幅画并回到 节点 \(u\) 的最小时间花费。

变成了一个树形背包问题。
暴力求解即可，边界为 \(f_{u,0} = 0\)，有：

\[f_{u,i} = \min_{j=1}^{}\{f_{u,i-k} + f_{v,k} + 2\times (u,v)\} \]

对于叶节点，有：

\[f_{u,i} = 5\times i \]

注意转移时不可直接更新 \(f_{u,i}\)，会造成以新换新。
倒序枚举 \(i\)，使 \(f_{root,i}<T\) 的第一个 \(i\) 即为答案。

由于是二叉树，复杂度为 \(O(n^3)\) 级别，期望得分 \(100\text{pts}\)。

发现是优美的二叉树，做树形背包小题大做了。
可直接枚举 左右儿子中选择的数量来更新答案。
有：

\[f_{u,i} = \min\{f_{v1,j} + 2\times (u,v_1) + f_{v2,i-j}+2\times (u,v_2)\} \]

复杂度 \(O(n^3)\) 级别，期望得分 \(100\text{pts}\)。

代码实现

//知识点:DP 
/*
By:Luckyblock
实际上是一个树上背包问题。 
手玩可知，数据范围较小。 
又是优美至极的二叉树，暴力求即可。 
*/
#include <cstdio>
#include <ctype.h>
#include <cstring>
#include <algorithm>
#define ll long long
const int kMaxn = 1010;
const int kMaxT = 610;
//=============================================================
struct Edge {
  int v, w, ne;
} e[kMaxn << 1];
int n, T, node_num, edge_num, head[kMaxn], tmp[kMaxn];
int val[kMaxn], sum[kMaxn];
int f[kMaxn][kMaxT];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void AddEdge(int u, int v, int w) {
  e[++ edge_num].v = v, e[edge_num].w = w;
  e[edge_num].ne = head[u], head[u] = edge_num;
}
void Input(int u) {
  int v = ++ node_num, x = read(), y = read();
  AddEdge(u, v, x);
  if (y) {
    val[v] = sum[v] = y;
    return ;
  }
  Input(v), Input(v);
  for (int i = head[v]; i; i = e[i].ne) sum[v] += sum[e[i].v]; 
}  
void Dfs(int u) {
  f[u][0] = 0;
  for (int i = head[u]; i; i = e[i].ne) {
    int v = e[i].v, w = e[i].w;
    Dfs(v);
    for (int j = 0; j <= sum[u]; ++ j) tmp[j] = f[u][j];
    for (int j = 1; j <= sum[u]; ++ j) {
      for (int k = 1; k <= j; ++ k) {
        tmp[j] = std :: min(tmp[j] ,f[u][j - k] + f[v][k] + 2 * w);
      }
    }
    for (int j = 0; j <= sum[u]; ++ j) f[u][j] = tmp[j];
  }
  
  if (val[u]) {
    for (int i = 1; i <= val[u]; ++ i) f[u][i] = 5 * i;
    return ;
  }
}
//=============================================================
int main() {
  T = read(); 
  Input(0); 
  for (int i = head[0]; i; i = e[i].ne) sum[0] += sum[e[i].v]; 
  
  memset(f, 20, sizeof(f));
  Dfs(0);
  for (int i = sum[0]; i >= 0; i --) {
    if (f[0][i] < T) {
      printf("%d", i);
      break ;
    }
  }
  return 0;
}

推荐阅读