[cf1485e]Move and Swap(dp)
2346 단어 dp
그리고 교환 조작이 결과에 어떻게 영향을 미칠지 고려한다.만약 u'와 u를 교환하여 dp[u]를 업데이트하는 데 사용한다면 계산된 결과는 dp[u]=max(dp[v'])+abs(a1[u']-a1[u])이어야 한다.
이런 사고방식이 생겼다. 가장자리를 연결한 후에 먼저 깊이 있는 검색을 하고 각 노드의 깊이, 각 층의 최대치와 최소치를 기록한다.다시 노드를 깊이에 따라 큰 것부터 작은 것까지 순서를 정한다. 왜냐하면 위의 두 번째 방정식을 통해 알 수 있듯이 우리는 각 노드의 최대 아들이 필요할 뿐만 아니라 그것과 같은 층의 노드의 최대 아들도 필요하다.첫 번째 업데이트는 조금씩 하면 됩니다.두 번째는 같은 층에 가장 큰 m1=maxson[u]+a1[u]와 m2=maxson[u]-a1[u]를 기록한 다음에 이 층을 모두 통계한 다음에 dp[u]=max(dp[u], m1-a1[u], m2+a1[u])를 통일적으로 업데이트해야 한다.
대충 그렇겠지.매번 초기화해야 할 여러 그룹의 데이터를 기억하세요.그리고 롱롱 켜고... 울었던 기억이 나요.
#include
#include
#include
#define ll long long
using namespace std;
const int N=200010;
struct edge{
int y,next;
}data[N*2];
struct node{
int x,id;
}a1[N];
int t,n,num,h[N],dep[N],d,mn[N],mx[N],fa[N];
ll dp[N],m1,m2,mson[N];
inline int read(){
int x=0,f=0;char ch=getchar();
while(ch'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}
inline ll min1(ll i,ll j){return ij?i:j;}
inline void addedge(int u,int v){
data[++num].y=v,data[num].next=h[u],h[u]=num;
data[++num].y=u,data[num].next=h[v],h[v]=num;
}
void dfs1(int u,int f){
fa[u]=f;
for(int i=h[u],v;i!=-1;i=data[i].next){
v=data[i].y;
if(v==f)continue;
dep[v]=dep[u]+1;
d=max1(dep[v],d);
if(a1[v].x>mx[dep[v]])mx[dep[v]]=a1[v].x;
if(a1[v].xdep[j.id];}
int main(){
t=read();
dep[0]=a1[0].id=0;
for(int i=1;i<=200000;++i)mn[i]=1e9+10,mx[i]=0;
while(t--){
n=read();num=0;
dep[1]=d=1;
for(int i=1;i<=n;++i)h[i]=-1;
for(int i=2,x;i<=n;++i){
x=read();addedge(x,i);
}
a1[1].id=1,a1[1].x=0;
for(int i=2;i<=n;++i){a1[i].id=i;a1[i].x=read();}
dfs1(1,0);
sort(a1+1,a1+n+1,cmp1);
for(int k=1,jj=1,u;k<=n;++k){
if(dep[a1[k].id]!=dep[a1[k-1].id]){
for(int j=jj;j 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
