虽然AC了,但还是求助一些玄学的问题
查看原帖
虽然AC了,但还是求助一些玄学的问题
754467
f_hxr_楼主2024/5/23 14:27

虽然有K个“小团体”,但还是可能有部分小团体没人。

于是我就在代码里加了continue(第二十五行)

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=5005+7;
const LL inf=1e18;
int N,M,K;
LL X;
LL A[maxn],C[maxn];
vector<LL>P[maxn];
int PanWuJiecnt[maxn];
LL dp[maxn][maxn],f[2][maxn][2];
int main(){
	
	scanf("%d %d %d %lld",&N,&M,&K,&X);
	for(int i=1;i<=N;i++)scanf("%lld",&A[i]);
	for(int i=1;i<=N;i++){
		scanf("%lld",&C[i]);
		P[C[i]].push_back(i);
		PanWuJiecnt[C[i]]++;
	}
	int PanWuJie1=0;for(int i=1;i<=K;i++)if(PanWuJiecnt[i]&1)++PanWuJie1;if(PanWuJie1>M){printf("Impossible");return 0;}
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0;
	for(int T=1;T<=K;T++){ 
		if(P[T].size()==0)continue;//here!!!!!!!!!!
		//assert(P[T].size()!=0);
		int cz=P[T].size();
		for(int i=0;i<=M;i++)f[0][i][0]=f[0][i][1]=inf;
		f[0][0][0]=0;
		int now=1;
		for(int i=1;i<=P[T].size();i++){
			for(int j=0;j<=M;j++){
				f[now][j][0]=f[now^1][j][1]+A[P[T][i-1]]+X*P[T][i-1];
				if(j>0)f[now][j][0]=min(f[now][j][0],f[now^1][j-1][0]);
				
				f[now][j][1]=f[now^1][j][0]+A[P[T][i-1]]-X*P[T][i-1];
				if(j>0)f[now][j][1]=min(f[now][j][1],f[now^1][j-1][1]);
			}
			now^=1;
		}
		for(int i=0;i<=P[T].size();i++){
			//cout<<f[now^1][i][0]<<' ';
			for(int j=i;j<=N;j++){
				dp[T][j]=min(dp[T][j],dp[T-1][j-i]+f[P[T].size()&1][i][0]);	
			}
		}
		//cout<<endl;
	}
	LL ans=inf;
	for(int i=0;i<=M;i++)ans=min(ans,dp[K][i]);
	printf("%lld",ans);
	return 0;
}

但是它却WA了。。。

然而,当我把continue去掉后,雀又AC了

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=5005+7;
const LL inf=1e18;
int N,M,K;
LL X;
LL A[maxn],C[maxn];
vector<LL>P[maxn];
int PanWuJiecnt[maxn];
LL dp[maxn][maxn],f[2][maxn][2];
int main(){
	
	scanf("%d %d %d %lld",&N,&M,&K,&X);
	for(int i=1;i<=N;i++)scanf("%lld",&A[i]);
	for(int i=1;i<=N;i++){
		scanf("%lld",&C[i]);
		P[C[i]].push_back(i);
		PanWuJiecnt[C[i]]++;
	}
	int PanWuJie1=0;for(int i=1;i<=K;i++)if(PanWuJiecnt[i]&1)++PanWuJie1;if(PanWuJie1>M){printf("Impossible");return 0;}
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0;
	for(int T=1;T<=K;T++){ 
		//if(P[T].size()==0)continue;//here!!!!!!!!!!
		//assert(P[T].size()!=0);
		int cz=P[T].size();
		for(int i=0;i<=M;i++)f[0][i][0]=f[0][i][1]=inf;
		f[0][0][0]=0;
		int now=1;
		for(int i=1;i<=P[T].size();i++){
			for(int j=0;j<=M;j++){
				f[now][j][0]=f[now^1][j][1]+A[P[T][i-1]]+X*P[T][i-1];
				if(j>0)f[now][j][0]=min(f[now][j][0],f[now^1][j-1][0]);
				
				f[now][j][1]=f[now^1][j][0]+A[P[T][i-1]]-X*P[T][i-1];
				if(j>0)f[now][j][1]=min(f[now][j][1],f[now^1][j-1][1]);
			}
			now^=1;
		}
		for(int i=0;i<=P[T].size();i++){
			//cout<<f[now^1][i][0]<<' ';
			for(int j=i;j<=N;j++){
				dp[T][j]=min(dp[T][j],dp[T-1][j-i]+f[P[T].size()&1][i][0]);	
			}
		}
		//cout<<endl;
	}
	LL ans=inf;
	for(int i=0;i<=M;i++)ans=min(ans,dp[K][i]);
	printf("%lld",ans);
	return 0;
}

有谁知道为什么吗???

2024/5/23 14:27
加载中...