P4253 SCOI2015 小凸玩密室
一道紫色的 dp。
思路
首先读题：
要保证任意时刻所有被点亮的灯泡必须连通
在点亮一个灯泡后必须先点亮其子树所有灯泡才能点亮其他灯泡
考虑设 \(g[u][1]\) 为 \(u\) 子树第一个被选中的是子树的根的代价，\(g[u][0]\) 为 \(u\) 子树内第一个选中的点不是子树的根（全局第一个选中的点在 \(u\) 子树内且不为 \(u\)）。
我们发现转移与距离有关，遂加一维。
设 \(g[u][1][j]\) 为 \(u\) 子树第一个被选中的是子树的根的代价，且 \(u\) 子树选完后，最后一个被选的点到 \(u\) 的距离为 \(j\)。
\(g[u][0][j]\) 为 \(u\) 子树内第一个选中的点不是子树的根，且 \(u\) 子树选完后，最后一个被选的点到 \(u\) 的距离为 \(j\)。
反复思考题目中的两个条件，你会发现，每个子树内只有最后一个选中的是叶子节点才是合法情况。
但再思考一下，发现如果一个节点只有一个儿子，还是有可能自己成为子树内最后一个选中的节点。
不过这是一棵完全二叉树。
那么出现这种情况的点最多只会有一个，这种点特殊考虑就可以了。
我们可以写出一般情况下的二叉树转移方程：
设 \(v_1\)、\(v_2\) 为 \(u\) 的两个儿子，两条边的长度为 \(d[v_1]\) 和 \(d[v_2]\)，\(dis[u]\) 为 \(u\) 子树中叶子节点到 \(u\) 节点的距离集合。
\[g[u][1][i+d[v_2]]=\min_{j\in dis[v_1]}(g[v_1][1][j]+a[v_2]\times (j+d[v_2]+d[v_1]))+g[v_2][1][i]+a[v_1]\times d[v_1] \]其中 \(i\in dis[v_2]\)。
这条方程的含义是：点亮 \(u\) 以后先去点亮 \(v_1\)，再从 \(v_1\) 子树内的叶子节点点亮 \(v_2\)，最后在 \(v_2\) 的叶子节点点完 \(u\) 子树，此时距离 \(v_2\) 节点是 \(i\)，那么距离 \(u\) 节点就是 \(i+d[v_2]\) 了。
至于为什么都是 \(g[v][1][j]\) 在转移呢，因为父亲都子树内第一个点亮的了，那么想要点亮其它点肯定要先点亮儿子呀。
类似的可以写出：
\[g[u][1][i+d[v_1]]=\min_{j\in dis[v_2]}(g[v_2][1][j]+a[v_1]\times (j+d[v_1]+d[v_2]))+g[v_1][1][i]+a[v_2]\times d[v_2] \]其中 \(i\in dis[v_1]\)。
然后我们考虑针对 \(g[u][0][i]\) 的转移，此时自己的儿子可以是他所在子树内先点亮的，也可以是后点亮的，都是合法的，对于另外一个儿子肯定就是先点亮根的喽，那么有转移：
\[g[u][1][i+d[v_2]]=\min(\min_{j\in dis[v_1]}(g[v_1][0][j]+(j+d[v_1])\times a[u]),\min_{j\in dis[v_1]}(g[v_1][1][j]+(j+d[v1])\times a[u]))+d[v_2]\times a[v_2]+g[v_2][1][i] \]类似的我们需要把 \(v_1\) 和 \(v_2\) 换过来，在写一遍这个转移，下面就不再写了。
观察转移方程，注意到我们每个方程中含 \(j\) 的那一项，对于每一个 \(u\) 来说都是一个固定值。
所以每一次提前求出含 \(j\) 项的最小值，然后枚举 \(i\) 就可以转移了。
考虑时间复杂度：
每次转移都相当于遍历一遍自己子树内叶子节点到自己的距离。
所以每一层的转移复杂度都是 \(O(叶子节点个数)\)。
然而根据完全二叉树，层数不会超过 \(\log n\) 层，总复杂度就是 \(O(叶子节点个数 \log n)\)。
CODE
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e5+5;
int n;
ll d[maxn],a[maxn];
vector<ll>vec[maxn],dis[maxn];
unordered_map<ll,ll>g[maxn][2];
inline void solve1(int u,int v1,int v2)//1 的转移
{
ll res=1e18;
for(auto j:dis[v1])//提前求含 j 项
res=min(res,g[v1][1][j]+a[v2]*(j+d[v2]+d[v1])+a[v1]*d[v1]);
for(auto j:dis[v2])
{
if(g[u][1][j+d[v2]]==0) g[u][1][j+d[v2]]=1e18;
g[u][1][j+d[v2]]=min(res+g[v2][1][j],g[u][1][j+d[v2]]);
}
}
inline void solve2(int u,int v1,int v2)//0 的转移
{
ll res0=1e18,res1=1e18;
for(auto j:dis[v1])
res0=min(res0,g[v1][0][j]+(j+d[v1])*a[u]+d[v2]*a[v2]),res1=min(res1,g[v1][1][j]+(j+d[v1])*a[u]+d[v2]*a[v2]);
for(auto j:dis[v2])
{
if(g[u][0][j+d[v2]]==0) g[u][0][j+d[v2]]=1e18;
g[u][0][j+d[v2]]=min(res0+g[v2][1][j],g[u][0][j+d[v2]]);
g[u][0][j+d[v2]]=min(res1+g[v2][1][j],g[u][0][j+d[v2]]);
}
}
inline void dfs(int u)
{
int v1=u*2,v2=u*2+1;
if(v1>n&&v2>n){vec[u].push_back(u);dis[u].push_back(0);return ;}
dfs(v1);
if(v2<=n) dfs(v2);
else
{
g[u][1][d[v1]]=d[v1]*a[v1];g[u][0][0]=d[v1]*a[u];
g[u][1][0]=1e18;g[u][0][d[v1]]=1e18;
vec[u].push_back(v1);vec[u].push_back(v2);dis[u].push_back(d[v1]);dis[u].push_back(0);
return ;
}
solve1(u,v1,v2);solve1(u,v2,v1);//v1,v2 转移方程是一样的
solve2(u,v1,v2);solve2(u,v2,v1);
vec[u].insert(vec[u].end(),vec[v1].begin(),vec[v1].end());
vec[u].insert(vec[u].end(),vec[v2].begin(),vec[v2].end());
dis[u].resize(vec[u].size());//处理 u 与叶子节点距离
for(int i=0;i<vec[v1].size();i++) dis[u][i]=dis[v1][i]+d[v1];
for(int i=0;i<vec[v2].size();i++) dis[u][i+vec[v1].size()]=dis[v2][i]+d[v2];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=2;i<=n;i++) scanf("%lld",&d[i]);
dfs(1);
ll ans=1e18;
for(auto j:dis[1]) ans=min(ans,min(g[1][1][j],g[1][0][j]));
printf("%lld\n",ans);
}
后记
竟然是第一道独立做出来的紫色 dp。
标签：min,int,点亮,v1,v2,小凸,SCOI2015,P4253,dis From： https://www.cnblogs.com/binbinbjl/p/18260381