首先，因为 \(w_i\le 10^6\)，有点大，所以我们想方设法把他变小一点。
设一个快为 \(w_i=k\times x+r\)。其实，如果我们把他分为 \(x\) 个大小为 \(k\) 的块，然后一个大小为 \(r\) 的块是最优的。因为切成其他的大小的块，我们可以调整成这种切法，答案不是更劣。比如说，有 9 3 4 这三个快，\(k=8\)。你可以使 \(9=4+5\)，然后 \(3,5\)、\(4,4\) 配对。但是你也可以 \(9=8+1\)，然后 \(3,4,1\)、\(8\) 配对。
然后我们就把 \(w_i\) 弄成了 \(<k\) 的大小。（其实就是模 \(k\)）。注意这个切也要算入答案。
现在考虑另一件事情。你有若干个 \(<k\) 大小的块，计个数为 \(cnt_1,cnt_2,\cdots cnt_{k-1}\)。对于 \(1\le i < \frac{k}{2}\)，我们可以使 \(i\) 与 \(k-i\) 配对，即对于 \(1\le i < \frac{k}{2}\)，\(cnt_{i}\) 和 \(cnt_{k-i}\) 均减 \(\min(cnt_i,cnt_{k-i})\)，不需要任何切。发现这样切完以后，\(cnt_i>0\) 的 \(i\) 最多有 \(4\) 个（\(k=8\) 的情况），即 \(1\) 或 \(7\)，\(2\) 或 \(6\)，\(3\) 或 \(5\) 和 \(4\)。设这些非零的数为 \(b_0\sim b_3\)。如果小于四个，\(b_i\) 就是 \(0\)。
考虑，这些块的个数均小于 \(n\)，也就是 \(100\)。实际上，个数的组合最多有 \(25^4\) 种。这时候就可以 dp 了。设 \(dp_{i,j,k,l}\) 代表用 \(i\) 个 \(b_0\)，\(j\) 个 \(b_1\)，\(k\) 个 \(b_2\)，\(l\) 个 \(b_3\) 的，的什么呢？
这时候就要进行一个题目的转化。我们不难发现，原来的题目等同于：
给你一些 \(<k\) 大小的方块。设他们的和为 \(a\times k\)。现在，把他们分成若干组，设为 \(b\) 组，使得每一组的大小和都是 \(k\) 的倍数。最大化 \(a-b\)。
这样为什么是对的呢？不切的情况下，显然 \(a=b\)。如果你切了一下，那就一定要和另一个（或多个）方块组合，就会少掉一组，即 \(b=b-1\)。
所以，dp 就是最多能分出的组的个数。转移很显然。
复杂度 \(\mathcal{O}(n^4)\)，但其实很松。
Code
#include <bits/stdc++.h>
using namespace std;
#define de(x) cout<<#x<<"="<<x<<endl
using ll = long long;
int n,K,a[111],ans;
int cnt[8],sum,id[4],c[4];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>K;
for (int i=0; i<n; i++){
cin>>a[i];
ans+=a[i]/K-(a[i]%K==0);
cnt[a[i]%K]++;
}
for (int i=1; i<K/2; i++){
int mnu=min(cnt[i],cnt[K-i]);
cnt[i]-=mnu;
cnt[K-i]-=mnu;
}
int tot=0;
for (int i=1; i<K; i++){
if (cnt[i]){
id[tot++]=i;
c[tot-1]=cnt[i];
sum+=i*cnt[i];
}
}
ans+=sum/K;
int dp[c[0]+1][c[1]+1][c[2]+1][c[3]+1];
for (int i=0; i<c[0]+1; i++){
for (int j=0; j<c[1]+1; j++){
for (int k=0; k<c[2]+1; k++){
for (int l=0; l<c[3]+1; l++){
auto &pd=dp[i][j][k][l];
pd=0;
if (i){
pd=max(pd,dp[i-1][j][k][l]);
}
if (j){
pd=max(pd,dp[i][j-1][k][l]);
}
if (k){
pd=max(pd,dp[i][j][k-1][l]);
}
if (l){
pd=max(pd,dp[i][j][k][l-1]);
}
if ((i*id[0]+j*id[1]+k*id[2]+l*id[3])%K==0){
pd++;
}
}
}
}
}
ans-=dp[c[0]][c[1]][c[2]][c[3]]-1;
cout<<ans<<endl;
return 0;
}
// don't waste time!!!