因为边界 l ， r 是线性移动的，所以答案可以线性改变，直接用set维护连续段（小于l的和大于r的）的个数，并维护ans即可。 因为set的一个小错误调了两个小时，代码打成了一坨，结果最后改完了但是没交上。 首先第一句话可以保证每两颗相邻的树之间的标号是连续的，所以对于叶子节点来说只需要关注最小的和最大的。 那么dp数组只记相关节点的状态即可。f[i][0/1][0/1][0/1]表示对于以i点为根节点的子树内i、最小的叶子节点、最大的叶子节点选没选就可以转移了。 然后就是大力分讨，但分了一个下午也没分出来，最后发现直接递推无需分讨。 题解说是网络流的切糕模型板子，没学呢，先挂个标记。 生成函数。（我要是把网络流和多项式弄懂了就学这个） [========] [========] 今天也被薄纱了，开题策略确实有问题，可能看题不够深吧，patience。T1、商品
码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int,int> pii;
#define fi first
#define se second
#define ps emplace_back
#define mk make_pair
const int N=1e6+10;
inline ll read(){
char c=getchar();ll x=0,f=1;
while(!isdigit(c))(c=='-'?f=-1:f=1),c=getchar();
while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,d,a[N],b[N];
vector<int> v[N];
struct jj{
mutable int l,r;
inline bool operator <(const jj&x)const{return l<x.l;}
};
set<jj>s,s1;
inline void ins(int pos){
auto it=s.insert({pos,pos}).fi,man=it;
if((++man)!=s.end()){
++it;
if(it->l==pos+1){
// ans-=a[pos]-max(la,a[pos+1]);
it->l=pos;
auto i=it;
s.erase(--i);
}
else --it;
// else ans-=a[pos+1]-a[pos];
}
if(it!=s.begin()){
int r=it->r;
--it;
if(it->r==pos-1){
// ans-=a[pos]-max(la,a[pos-1]);
it->r=r;
s.erase(++it);
}
// else ans-=a[pos-1]-a[pos];
}
}
inline void del(int pos){
auto it=s1.lower_bound({pos,pos});
if(it==s1.end()||it->l>pos)--it;
if(it->l!=pos){
// ans-=min(la,a[pos-1])-a[pos];
int l=it->l;
it->l=pos,s1.insert({l,pos-1});
}
if(it->r!=pos){
// ans-=min(la,a[pos+1])-a[pos];
int r=it->r;
it->r=pos;s1.insert({pos+1,r});
}
s1.erase({pos,pos});
}
ll ans=0,anss=0;
main(){
#ifndef ONLINE_JUDGE
freopen("goods.in","r",stdin);
freopen("goods.out","w",stdout);
#endif
//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
n=read(),d=read();
for(int i=1;i<=n;++i){
b[i]=a[i]=read();
}
// for(int i=1;i<n;++i)
// ans+=abs(a[i]-a[i+1]);
sort(b+1,b+1+n);
int n1=unique(b+1,b+1+n)-b-1;
// cout<<b[2]<<endl;
for(int i=1;i<=n;++i){
int pos=lower_bound(b+1,b+1+n1,a[i])-b;
v[pos].ps(i);
}
s1.insert({1,n});
b[0]=b[1];
for(int i=1,k=1,l,r;i<=n1;++i){
l=b[i],r=l+d;
ans-=2ll*s.size()*(b[i]-b[i-1]);
if(s.size()){
auto it=s.begin();
if(it->l==1ll)ans+=b[i]-b[i-1];
auto itt=s.rbegin();
if(itt->r==n)ans+=b[i]-b[i-1];
}
for(auto j:v[i])ins(j);
while(k<=n1&&b[k]<=r){
ans+=2ll*s1.size()*(b[k]-b[k-1]);
if(s1.size()){
auto it=s1.begin();
if(it->l==1)ans-=b[k]-b[k-1];
auto itt=s1.rbegin();
if(itt->r==n)ans-=b[k]-b[k-1];
}
for(auto j:v[k]){
del(j);
}
++k;
}
if(k>n1){
anss=max(ans,anss);break;
}
ll ko=ans;
ko+=2ll*s1.size()*(r-b[k-1]);
if(s1.size()){
auto it=s1.begin();
if(it->l==1)ko-=r-b[k-1];
auto itt=s1.rbegin();
if(itt->r==n)ko-=r-b[k-1];
}
anss=max({ans,ko,anss});
}
s.clear(),s1.clear();
s1.insert({1,n});
b[n1+1]=b[n1];
ans=0;
for(int i=n1,l,r,k=n1;i;--i){
r=b[i],l=r-d;
ans-=2ll*s.size()*(b[i+1]-b[i]);
if(s.size()){
auto it=s.begin();
if(it->l==1ll)ans+=b[i+1]-b[i];
auto itt=s.rbegin();
if(itt->r==n)ans+=b[i+1]-b[i];
}
for(auto j:v[i])ins(j);
while(k&&b[k]>=l){
ans+=2ll*s1.size()*(b[k+1]-b[k]);
if(s1.size()){
auto it=s1.begin();
if(it->l==1)ans-=b[k+1]-b[k];
auto itt=s1.rbegin();
if(itt->r==n)ans-=b[k+1]-b[k];
}
for(auto j:v[k])del(j);
--k;
}
if(k<=0){
anss=max(ans,anss);break;
}
ll ko=ans;
ko+=2ll*s1.size()*(b[k+1]-l);
if(s1.size()){
auto it=s1.begin();
if(it->l==1)ko-=b[k+1]-l;
auto itt=s1.rbegin();
if(itt->r==n)ko-=b[k+1]-l;
}
anss=max(anss,ko);
}
cout<<anss;
}
T2、价值
\[\Huge 学会读题
\]码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define ps emplace_back
#define mk make_pair
const int N=1e5+10;
const ll mod=998244353;
inline ll read(){
char c=getchar();ll x=0,f=1;
while(!isdigit(c))(c=='-'?f=-1:f=1),c=getchar();
while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
ll f[100005][2][2][2],n,xiao[N],da[N];
vector<int> son[N];
ll man[2][2][2];
int main(){
#ifndef ONLINE_JUDGE
freopen("value.in","r",stdin);
freopen("value.out","w",stdout);
#endif
//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
n=read();
for(int i=2;i<=n;++i){
son[read()].ps(i);
}
for(int i=n;i;--i){
if(!son[i].size())
xiao[i]=da[i]=i;
else {
xiao[i]=n+1;
for(auto j:son[i])
xiao[i]=min(xiao[i],xiao[j]),da[i]=max(da[i],da[j]);
}
}
for(int i=n;i;--i){
if(!son[i].size())f[i][0][0][0]=1;
else{
int j=son[i][0];
for(int l1=0;l1<2;++l1)
for(int l2=0;l2<2;++l2){
f[i][0][l1][l2]=(f[j][0][l1][l2]+f[j][1][l1][l2])%mod;
if(j!=xiao[i])f[i][1][l1][l2]=f[j][0][l1][l2];
}
if(j==da[j])(f[i][1][1][1]+=f[j][0][0][0])%=mod;
for(int k=1;k<son[i].size();++k){
int j=son[i][k];
memcpy(man,f[i],sizeof(man));
f[i][0][0][0]=f[i][0][0][1]=f[i][0][1][0]=f[i][0][1][1]=f[i][1][0][0]=f[i][1][0][1]=f[i][1][1][0]=f[i][1][1][1]=0;
bool f1=(k==1&&xiao[son[i][0]]==da[son[i][0]]),f2=(xiao[j]==da[j]),f3=(j==da[j]);
for(int l1=0;l1<2;++l1){
for(int l2=0;l2<2;++l2){
for(int l3=0;l3<2;++l3){
for(int r1=0;r1<2;++r1){
for(int r2=0;r2<2;++r2){
for(int r3=0;r3<2;++r3){
int i1,i2,i3;
//0 0
i1=l1,i2=l2,i3=r3;
(f[i][i1][i2][i3]+=(man[l1][l2][l3]*f[j][r1][r2][r3])%mod)%=mod;
//0 1
if(!l3&&!r2){
i1=l1,i2=l2|f1,i3=r3|f2;
(f[i][i1][i2][i3]+=(man[l1][l2][l3]*f[j][r1][r2][r3]%mod))%=mod;
}
//1 0
if(!l1&&!r1){
i1=1,i2=l2,i3=r3|f3;
(f[i][i1][i2][i3]+=(man[l1][l2][l3]*f[j][r1][r2][r3]%mod))%=mod;
}
//1 1
if(!l1&&!r1&&!l3&&!r2&&!f3){
i1=1,i2=l2|f1,i3=r3|f2|f3;
(f[i][i1][i2][i3]+=(man[l1][l2][l3]*f[j][r1][r2][r3]%mod))%=mod;
}
}
}
}
}
}
}
}
}
}
ll ans=0;
for(int i=0;i<2;++i)
for(int j=0;j<2;++j)
for(int k=0;k<2;++k)
ans+=f[1][i][j][k];
if(da[1]!=xiao[1])ans+=f[1][0][0][0]+f[1][1][0][0];
cout<<ans%mod;
}
T3、货币
T4、资本