虽然有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;
}
有谁知道为什么吗???