妹子简单dp WA求助
查看原帖
妹子简单dp WA求助
556545
Aaa_liang楼主2024/9/12 09:54

rt,WA了17个点,实在看不出来了求大佬捞捞QAQ!

#include<vector>
#include<cstring>
#include<iostream>
#define endl '\n'
#define inf 2147483640
using namespace std;
const int N=1e4+5;
int t,n,a,b,c,dp[2][N][N],siz[N],fas[N];
vector<int> edges[N];
void dfs(int x){
	siz[x]=0;
	if(!edges[x].size()){
		siz[x]=1,dp[1][1][x]=dp[0][0][x]=0;
		dp[0][1][x]=dp[1][0][x]=-inf;
		return;
	}
	dp[0][0][x]=0,dp[1][0][x]=1;
	for(int q=0;q<edges[x].size();q++){
		int l=edges[x][q];dfs(l);
		for(int i=siz[x]+1;i<=siz[x]+siz[l];i++) dp[0][i][x]=dp[1][i][x]=-inf;
		for(int i=siz[x];i>=0;i--){
			for(int j=siz[l];j>=0;j--){
				dp[1][i+j][x]=max(dp[1][i+j][x],dp[1][i][x]+dp[0][j][l]);
				dp[0][i+j][x]=max(dp[0][i+j][x],dp[0][i][x]+max(dp[1][j][l],dp[0][j][l]));
			}
		}
		siz[x]+=siz[l];
	} 
}
void solve(){
	for(int i=1;i<=n;i++) edges[i].clear(),siz[i]=0;
	cin>>n>>a>>b>>c;
	for(int i=2;i<=n;i++){
		cin>>fas[i];
		edges[fas[i]].push_back(i);
	}
	if(n==1){cout<<"Yes"<<endl;return;}
    if(c&1){cout<<"No"<<endl;return;}
    c>>=1;
	dfs(1);int p=c,q1=b-c+1,q0=b-c;
	if(q0<=siz[1]&&q0>=0&&dp[0][q0][1]>=p) cout<<"Yes"<<endl;
	else if(q1<=siz[1]&&q1>=0&&dp[1][q1][1]>=p) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>t;while(t--) solve();
	return 0;
}
2024/9/12 09:54
加载中...