[luogu4719] 동적 DP 템플릿 [동적 DP]
\(f {i, 0}\)는\(i\)를 선택하지 않은 최대 답안\(f {i, 1}\)가\(i\)를 선택한 최대 답안을 나타냅니다.
DP 방정식\(\begin{cases} f {i, 0} =\sum {son}max(f {son, 0}, f {son, 1})\\\\\\\\\\\f{i,1}=w_i+\sum_{son}f_{son, 0}\end{cases}\) 정답은\(max(f {rt, 0}, f {rt, 1})\
수정을 고려하여 우리는 이 나무를 숙련되게 분할한 후
설정\(g {i, 0}\)는\(i\)를 선택하지 않고\(i\)만 가벼운 아들이 있는 트리의 최대 답안을 선택할 수 있음을 나타내고,\(g {i, 1}\)는\(i\)를 선택한 최대 답안을 나타내며,\(son i\)는\(i\)의 무거운 아들을 나타낸다.
방정식\(\begin{cases} f {i, 0} = g {i, 0} +max(f {son i, 0}, f {son i, 1})\\\\\\\f{i,1}=g_{i,1}+f_{son i, 0}\end{cases}\) 정답은\(max(f {rt, 0}, f {rt, 1})\
행렬을 구성할 수 있습니다.\(\begin{bmatrix}g {i, 0}&g {i, 0}\g {i, 2}&-\infty\end{bmatrix}*\begin{bmatrix}f {son i, 0}\\\\\\\\\\\\\\\\f {son i, 1}\end{bmatrix}=\begin{bmatrix}f {i,\f {i,\f {0}\f {bmatrix})
중간 행렬 이동을 시뮬레이션해 봤는데 아직 잘 모르겠어요. == 다른 수정은 코드를 조회해 보면 다 알 수 있을 거예요.
#include
using namespace std;
#define ll long long
#define ls o<<1
#define rs o<<1|1
#define Max(x,y) ((x)>(y)?(x):(y))
const int N=1e5+10,inf=0x3f3f3f3f;
int n,m;
ll w[N],f[N][2];
templatevoid rd(t &x){
x=0;int w=0;char ch=0;
while(!isdigit(ch)) w|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=w?-x:x;
}
int head[N],tot=0;
struct edge{int v,nxt;}e[N<<1];
void add(int u,int v){e[++tot]=(edge){v,head[u]},head[u]=tot;}
int idx=0,dfn[N],id[N],fa[N],son[N],top[N],bot[N],sz[N];
void dfs1(int u,int ff){
fa[u]=ff,sz[u]=1;
for(int i=head[u],v,mxs=-1;i;i=e[i].nxt){
if((v=e[i].v)==ff) continue;
dfs1(v,u),sz[u]+=sz[v];
if(mxs>1;
if(x<=mid) mdf(ls,l,mid,x);
else mdf(rs,mid+1,r,x);
pup(o);
}
Matri query(int o,int l,int r,int x,int y){
if(x<=l&&r<=y) return t[o];
int mid=l+r>>1;
if(y<=mid) return query(ls,l,mid,x,y);
if(x>mid) return query(rs,mid+1,r,x,y);
return query(ls,l,mid,x,y)*query(rs,mid+1,r,x,y);
}
void build(int o,int l,int r){
if(l==r){
int u=id[l];ll g0=0,g1=w[u];
for(int i=head[u],v;i;i=e[i].nxt)
if((v=e[i].v)!=fa[u]&&v!=son[u])
g0+=Max(f[v][0],f[v][1]),g1+=f[v][0];
val[l]=t[o]=(Matri){g0,g0,g1,-inf};
return;
}
int mid=l+r>>1;
build(ls,l,mid),build(rs,mid+1,r);
pup(o);
}
void Mdf(int x,int k){
val[dfn[x]].a[1][0]+=k-w[x],w[x]=k;
while(x){
Matri a=query(1,1,n,dfn[top[x]],dfn[bot[x]]),b;
mdf(1,1,n,dfn[x]);
b=query(1,1,n,dfn[top[x]],dfn[bot[x]]);
x=fa[top[x]];if(!x) return;
int nw=dfn[x];
ll g0=a.a[0][0],g1=a.a[1][0],f0=b.a[0][0],f1=b.a[1][0];
val[nw].a[0][0]=val[nw].a[0][1]=val[nw].a[0][0]+Max(f0,f1)-Max(g0,g1),
val[nw].a[1][0]=val[nw].a[1][0]+f0-g0;
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
rd(n),rd(m);
for(int i=1;i<=n;++i) rd(w[i]);
for(int i=1,u,v;i
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.