「SCOI2015」小凸玩密室 https://loj.ac/problem/2009
虽然有心里在想一些奇奇怪怪的事情的原因, 不过还是写太久了..
不过这个题本身也挺厉害的
注意第一个被点亮的是任意选的, 我最开始压根没注意到
\(dp_{i,j}\) 代表 \(i\) 号点子树最后连出去的一个点连的是它第 \(j\) 层的祖先
\(f_{i,j}\) 代表 \(i\) 号点子树最后连出去的一个点连的是它第 \(j\) 层祖先的另一个儿子
然后我们就可以拼子树, 做换根了
要讨论只有一个儿子的情况
- Code:
- #include <cstdio>
- #include <cstring>
- #include <cctype>
- #include <algorithm>
- #define ll long long
- const int N=2e5+10;
- using std::min;
- template <class T>
- void read(T &x)
- {
- x=0;char c=getchar();
- while(!isdigit(c)) c=getchar();
- while(isdigit(c)) x=x*10+c-'0',c=getchar();
- }
- ll dp[2][N][20],a[N],edge[N],ans=1e18;
- int n,Log[N];
- #define ls (id<<1)
- #define rs (id<<1|1)
- void dfs(int id)
- {
- if(id<<1>n) return;
- dfs(ls),dfs(rs);
- for(int dep=Log[id];~dep;dep--)
- {
- if(ls<=n&&rs<=n)
- {
- dp[0][id][dep]=min(a[ls]*edge[ls]+dp[1][ls][Log[id]]+dp[0][rs][dep]
- ,a[rs]*edge[rs]+dp[1][rs][Log[id]]+dp[0][ls][dep]);
- dp[1][id][dep]=min(a[ls]*edge[ls]+dp[1][ls][Log[id]]+dp[1][rs][dep]
- ,a[rs]*edge[rs]+dp[1][rs][Log[id]]+dp[1][ls][dep]);
- }
- else if(ls<=n)
- {
- dp[0][id][dep]=a[ls]*edge[ls]+dp[0][ls][dep];
- dp[1][id][dep]=a[ls]*edge[ls]+dp[1][ls][dep];
- }
- }
- }
- void dfs0(int id,ll cost)
- {
- ans=min(ans,dp[0][id][Log[id]-1]+cost);
- if(ls<=n&&rs<=n)
- {
- dfs0(ls,a[rs]*edge[rs]+dp[0][rs][Log[id]-1]+cost);
- dfs0(rs,a[ls]*edge[ls]+dp[0][ls][Log[id]-1]+cost);
- }
- else if(ls<=n)
- dfs0(ls,edge[id]*a[id>>1]+cost);
- }
- int main()
- {
- int flag=0;read(n);
- for(int i=1;i<=n;i++) read(a[i]),Log[i]=Log[i>>1]+1;
- for(int i=2;i<=n;i++) read(edge[i]);
- memset(dp,0x3f,sizeof dp);
- for(int i=1;i<=n;i++)
- if(i<<1>n)
- {
- int typ=!(i&1),id=i>>1;ll sum=edge[i];
- for(int j=Log[i]-1;~j;j--)
- {
- dp[0][i][j]=a[id]*sum;
- dp[1][i][j]=a[id<<1|typ]*(sum+edge[id<<1|typ]);
- sum+=edge[id];
- typ=!(id&1);
- id>>=1;
- }
- }
- dfs(1);
- dfs0(1,0);
- printf("%lld\n",ans);
- return 0;
- }
- 2019.2.27
来源: http://www.bubuko.com/infodetail-2970068.html