思路我们设dp[i][j][0/1]表示该小团体前i个点用j次信息学名额当前是完整匹配/剩余了一个待匹配点的最小不满值。dp[i][j][0]min(dp[i-1][j-1][0],dp[i-1][j][1]a[i]x*i);dp[i][j][1]min(dp[i-1][j-1][1],dp[i-1][j][0]a[i]-x*i);然后因为每个小团体都是独立的所以设g[d][i](i1~m)数组。for(long long i0;im;i){ ansmin(ans,g[d][i]); } if(ans9e17){ printf(Impossible); return ~(-1); } // 也就是 // if(ans1e18){ // printf(Impossible); // return ~(-1); // }代码(求赞)#includebits/stdc.h using namespace std; //关于写#define int long long然后因为精度差距输出LLONG_MIN //于是用ctrl r将所有的int换成long long。 const long long N5e35; vectorlong longt[N]; long long n,m,d,x,cnt0,a[N],c[N],dp[N][N][2],g[N][N]; //dp[i][j][2]表 //dp[i][j][0]min(dp[i-1][j-1][0],dp[i-1][j][1]a[i]x*i); //dp[i][j][1]min(dp[i-1][j-1][1],dp[i-1][j][0]a[i]-x*i); int main(){ scanf(%lld%lld%lld%lld,n,m,d,x); for(long long i1;in;i){ scanf(%lld,a[i]); } for(long long i1;in;i){ scanf(%lld,c[i]); t[c[i]].push_back(i); } memset(g,0x3f,sizeof g); g[0][0]0; for(long long i1;id;i){ for(long long j0;jt[i].size();j){ for(long long k0;km;k){ dp[j][k][0]dp[j][k][1]1e18; } } dp[0][0][0]0; for(long long j1;jt[i].size();j){ for(long long k0;km;k){ dp[j][k][0]dp[j-1][k][1]a[t[i][j-1]]1ll*x*t[i][j-1]; dp[j][k][1]dp[j-1][k][0]a[t[i][j-1]]-1ll*x*t[i][j-1]; if(k){ dp[j][k][0]min(dp[j][k][0],dp[j-1][k-1][0]); dp[j][k][1]min(dp[j][k][1],dp[j-1][k-1][1]); } } } for(long long j0;jcnt;j){ for(long long k0;kt[i].size();k){ if(jkm){ g[i][jk]min(g[i][jk],g[i-1][j]dp[t[i].size()][k][0]); } } } cntt[i].size(); } long long ans1e18; for(long long i0;im;i){ ansmin(ans,g[d][i]); } if(ans9e17){ printf(Impossible); return ~(-1); } // 也就是 // if(ans1e18){ // printf(Impossible); // return ~(-1); // } printf(%lld,ans); return 0; }