#include<bits/stdc++.h>
using namespace std;
int f[1000][100],a[1005];
int main(){
freopen(“C.in”,“r”,stdin);
freopen(“C.out”,“w”,stdout);
int n,x;
cin>>n>>x;
for(int i=1;i<=n;i++){
cin>>a[i];
}
memset(f,-1,sizeof f);
f[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<x;j++){
f[i][j]=f[i-1][j];
}
for(int j=0;j<x;j++){
if(f[i-1][j]!=-1){
f[i][(j+a[i])%x]=max(f[i][(j+a[i])%x],f[i-1][j]+1);
}
}
}
int ans=1e9;
for(int i=0;i<x;i++){
if(f[n][i]!=-1){
ans=min(ans,(n-f[n][i])+(x-i)%x);
}
}
cout<<ans<<endl;
return 0;
}
哪错了？？？
dp求的是最小值，不能用max，dp数组初始化是可以初始化为正无穷
1 个赞