坠机：P16350 「Gensokyo OI Round 1」隙间插曲
fish_love_cat · · 题解
:::info[什么样的人生是失败的？（第十一弹）] 点击图片可以看见上一次坠机。
不会写树上背包这一块。初始化不完全这一块。对拍写一万年拍一万年这一块。看不懂 hack 这一块。看懂了 hack 看不懂自己的程序在干什么这一块。
赛后 3min 调完这一块。
拿大号作死打一把，现在可以回去打 div2 了 /hec
你怎么知道我的 d1t1 也爆了。如何提高树上面包水平。 :::
145pts 遗憾离场。
为什么会变成这样子呢？我问我自己。
贪心显然假。
只考虑尾删，显然转化成括号序列。
刻画头删的性质，我们发现可以把最左侧的失配左括号爆掉然后加入一个原先匹配的左括号。
这个加入括号的位置好像不是很可控，如果一个点包裹它的括号还没拆掉那么贡献会转移到包裹它的这个括号上。
我说这很像树形有没有懂的。
欧拉序也是括号串，考虑把树建出来，然后发现能够把一个树上的点转移出贡献当且仅当其所在根链全部解放。
这不就是选课吗！
对每个树跑树上背包即可，然后按照树的顺序倒着做一轮 dp 预处理，之后枚举移除前缀计算让出次数直接查表拿贡献即可。
还有问题！
实际上枚举前缀的时候有可能把某个树上的一些点给禁掉，于是不能直接套用，吗？
不管，注意到欧拉序剖下来长度
其实我认为这可以优化。
考虑到禁点的过程其实恰好是按照 dfs 的顺序来的，也就是说不会有儿子封了父亲没封的情况。
另外的，调整儿子访问顺序可以按照序列从后向前背包，子树信息依然可以准确处理。
因此我们可以树上背包的过程中额外处理一个假设我们前面的点全部删除，此时这些剩余断开的森林能带来的贡献，一样维护一个背包数组。
于是每次禁点后我们只需要在原先对于树信息背包的基础上加入一个合并好的背包即可。
这样时间复杂度应该是
难写的一批，不管了。如果假了喷似我就好，没假的话有没有人写一下这个做法 /hsh
反正有个奶龙
代码乱的起飞，有一些东西可能处理了压根没用到，如果恶心到你了致歉 /hanx
/*
14
11 48 13 33
27 29 22 0 70 0 0 0
54 86
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[1005],fa[1005];
stack<int>st;
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
vector<vector<int>>ve;
vector<vector<int>>id;
int tp;
int mx[1005],pt[1005];
int sum,ans;
int dp[1005][1005];
vector<int>son[1005];
int flg[1005];
int v[1005];
int b[1005];
int siz[1005];
int n;
void dfsiz(int x){
siz[x]=1;
for(int i:son[x])
dfsiz(i),siz[x]+=siz[i];
}
int tdp[2][1005][1005];
void dfs(int x,int op){
for(int i=0;i<=siz[x];i++)
tdp[0][x][i]=tdp[1][x][i]=-1e18;
tdp[0][x][1]=a[v[x]];
int flc=1,szum=1;
for(int i:son[x]){
dfs(i,op);
for(int k=0;k<=szum+siz[i];k++)
tdp[flc][x][k]=tdp[flc^1][x][k];
for(int j=1;j<=siz[i];j++)
for(int k=0;k<=szum;k++)
tdp[flc][x][j+k]=max(tdp[flc][x][j+k],
tdp[1][i][j]+tdp[flc^1][x][k]);
szum+=siz[i];
flc^=1;
}
for(int i=0;i<=siz[x];i++)
tdp[flc][x][i]=tdp[flc^1][x][i];
if(x==mx[find(x)]){
for(int i=0;i<siz[x];i++)
ve[op][i]=tdp[1][x][i+1];
}
}
signed main(){
memset(dp,-0x3f,sizeof dp);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++){
if(a[i])fa[i]=-1,st.push(i);
else{
for(int j=st.top()+1;j<i;j++)
if(a[j]==0&&!flg[j])
son[i].push_back(j),flg[j]=i;
v[i]=st.top();
fa[i]=st.top(),st.pop();
}
}
for(int i=n-1;i;i--)
if(fa[i]==-1&&i>=fa[i+1])fa[i]=fa[i+1];
else if(fa[i]!=-1&&fa[i+1]!=-1)fa[i]=min(fa[i],fa[i+1]);
for(int i=1;i<=n;i++)
if(fa[i]!=-1)mx[find(i)]=i;
else sum+=a[i];
ans=sum;
int lst=-2;
ve.push_back({});
id.push_back({});
for(int i=1;i<=n;i++){
if(fa[i]!=-1){
if(lst!=find(i))
lst=find(i),tp++,
ve.push_back({}),
id.push_back({});
if(a[i])
ve[tp].push_back(a[i]),
id[tp].push_back(i);
}
pt[i]=tp;
}
for(int i=1;i<=n;i++)
if(fa[i]!=-1&&mx[find(i)]==i)
dfsiz(i),dfs(i,pt[i]);
dp[tp+1][0]=0;
for(int i=tp;i;i--){
for(int k=0;k<=n;k++)
dp[i][k]=dp[i+1][k];
for(int j=0;j<ve[i].size();j++)
for(int k=0;k<=n-(j+1);k++)
dp[i][k+j+1]=max(dp[i][k+j+1],dp[i+1][k]+ve[i][j]);
}
for(int i=1;i<=n;i++)
dp[tp+1][i]=0;
int cnt=0;
for(int i=1;i<=n;i++)
if(fa[i]==-1){
sum-=a[i];
cnt++;
ans=max(ans,sum+dp[pt[i]+1][cnt]);
}else if(a[i]){
for(int j=1;j<=i;j++)
b[j]=a[j];
int qwq=0;
for(int j=1;j<=i;j++)
if(fa[j]!=-1&&find(j)==find(i)&&a[j])
a[j]=1e13,qwq++;
dfs(mx[find(i)],pt[i]);
ans=max(ans,sum+dp[pt[i]+1][cnt]);
for(int j=qwq;j<ve[pt[i]].size()&&cnt+qwq-j-1>=0;j++)
ans=max(ans,sum+(int)(dp[pt[i]+1][cnt+qwq-j-1]+ve[pt[i]][j]-qwq*(1e13)));
for(int j=1;j<=i;j++)
a[j]=b[j];
}
cout<<ans;
return 0;
}
//「——所以，确定那头怪物是『黑玛瑙〈Black Agate〉』吧？用四肢爬行？」
//「呵……呵呵呵呵呵……」
// 艾瑟雅俯首，用阴沉的表情笑了笑。
//「啊！真是的！这是怎样啊！」
// 接着，她情绪爆发了。
//「我的脑容量已经不堪负荷了啦！
// 爱洛瓦、菈恩还有那个混账，一个个都把我当成什么啦？只会给我找一大堆麻烦！就不能偶尔让我沉浸在感伤的回忆里吗！
// 为什么那个人偏偏要选在这个时间点，特地用既滑稽又吓人的方式登场啊！」