60分求hack,WA 4--7(dp做法),玄关
查看原帖
60分求hack,WA 4--7(dp做法),玄关
1396852
OWPPIE楼主2025/7/3 20:08
#include<bits/stdc++.h>
using namespace std;
long long n,t[1005],dp[1005][5];
vector<long long> a[1005],q;
int dfs(int x){
	for(int i=0;i<a[x].size();i++){
		if(t[a[x][i]]==0){
			t[a[x][i]]=x;
			q.push_back(a[x][i]);
		}
	}
	return 0;
}
int main(){
	cin>>n;
    // cout<<n%100;
    // return 0;
	for(int i=2;i<=n;i++){
		int x;
		cin>>x;
		a[i].push_back(x);
		a[x].push_back(i);
	}
	t[1]=-1;
	q.push_back(1);
	for(int i=0;i<q.size();i++){
		dfs(q[i]);
	}
	for(int i=q.size()-1;i>=0;i--){
		dp[q[i]][0]=1;
        int x=q[i];
        if(a[x].size()==1&&i!=0) {
            dp[q[i]][1]=1e9;
            dp[q[i]][2]=1e9;
            continue;
        }
		long long b1=0,b2=0,b3=0,minn=1e9,minn1=1e9,mi=1e9,cv=0;
		for(int j=0;j<a[x].size();j++){
			if(a[x][j]==t[x]) continue;
			long long kl=min({dp[a[x][j]][0],dp[a[x][j]][1],dp[a[x][j]][2],dp[a[x][j]][4]});
			if(kl==dp[a[x][j]][0]){
                b1=1;
            }else{
                long long yu=dp[a[x][j]][0]-min({dp[a[x][j]][1],dp[a[x][j]][2],dp[a[x][j]][4]});
                if(minn>=yu){
                    minn=yu;
                    if(kl==dp[a[x][j]][4]&&min({dp[a[x][j]][0],dp[a[x][j]][1],dp[a[x][j]][2]})!=dp[a[x][j]][4]){
                         cv=max(cv,min({dp[a[x][j]][0],dp[a[x][j]][1],dp[a[x][j]][2]})-dp[a[x][j]][4]);
                    }else{
                        cv=0;
                    }
                } 
            }
			if(kl==dp[a[x][j]][1]) b2=1;
			else minn1=min(minn1,dp[a[x][j]][1]-min({dp[a[x][j]][0],dp[a[x][j]][4],dp[a[x][j]][2]}));
            if(kl==dp[a[x][j]][4]&&min({dp[a[x][j]][0],dp[a[x][j]][1],dp[a[x][j]][2]})!=dp[a[x][j]][4]){
                mi+=(min({dp[a[x][j]][0],dp[a[x][j]][1],dp[a[x][j]][2]})-dp[a[x][j]][4]);
                b3=1;
            } 
			dp[x][0]+=min({dp[a[x][j]][0],dp[a[x][j]][1],dp[a[x][j]][2],dp[a[x][j]][3],dp[a[x][j]][4]});
			dp[x][3]+=kl;
			dp[x][4]+=kl;
			dp[x][1]+=kl;
			dp[x][2]+=kl;
		}
        //cout<<b1<<"--"<<b2<<"--"<<b3<<'\n';
		if(b2==0){
			dp[x][2]+=minn1;
		}
		if(b1==0){
            if(b3){
               dp[x][4]+=min(minn,mi-cv); 
            }
			dp[x][1]+=minn;
		}
        //cout<<x<<" "<<dp[x][0]<<" "<<dp[x][1]<<" "<<dp[x][2]<<" "<<dp[x][3]<<" "<<dp[x][4]<<'\n';
	}
	cout<<min({dp[1][0],dp[1][1],dp[1][2]});
	return 0;
}
2025/7/3 20:08
加载中...