洛谷P1270 访问美术馆

题目

树形DP，首先考虑递归建图，类似于线段树的中序遍历。然后取状态dp[i][j]表示i点花费j时间所偷到的最多的画，有方程：

\(dp[now][nwt] = max(dp[now][nwt], dp[lso][i] + dp[rso][nwt - i - data[now].t]);\)

注意三点：

1. 可能一次偷不完所有的画

2. 来回要路径花费时间乘二

3. 要在t之前走，因此t要减一

   #include <bits/stdc++.h>
   using namespace std;
   int t, dp[3001][3001];
   struct a {
   int t, sum;
   int ls, rs;
   }data[101001];
   void init(int now)
   {
   cin >> data[now].t >> data[now].sum;//n个节点
   data[now].t *= 2;
   if (!data[now].sum)
   {
       data[now].ls = now << 1, data[now].rs = now << 1 | 1;
       init(now << 1), init(now << 1 | 1);
   }
   }
   void dfs(int now, int nwt)
   {
   int lso = data[now].ls, rso = data[now].rs;
   if (!nwt || dp[now][nwt] > 0) return;
   if (data[now].sum)
   {
       dp[now][nwt] = min(data[now].sum, (nwt - data[now].t) / 5);//可能偷不了五秒 
       return;
   }
   for (int i = 0; i + data[now].t <= nwt; i++)
   {
       dfs(data[now].ls, i);
       dfs(data[now].rs, nwt - i - data[now].t);
       dp[now][nwt] = max(dp[now][nwt], dp[lso][i] + dp[rso][nwt - i - data[now].t]);
   }
   }
   int main()
   {
   scanf("%d", &t);
   t--;
   init(1);
   dfs(1, t);
   printf("%d", dp[1][t]);
   return 0;
   } 

洛谷P1270 访问美术馆

原文：https://www.cnblogs.com/liuwenyao/p/11740984.html