题解：AT_abc192_f [ABC192F] Potion
_zSqr_Mahiro_Oyama_
·
·
题解
题意
在 N 个数里选取任意个数，设个数为 K，求 \frac{X-\sum A_i}{K} 最小值。
思路
首先可以发现所有数的总和不会超过 X。
设个数为 $K$，求出 $X \bmod K$，记为 $x$；求出 $A_i \bmod K$，记为 $a_i$。我们现在要选出一些数，使它们的总和取模 $K$ 等于 $x$，且选取个数为 $K$ 才能符合要求。
考虑 dp，设 $dp_{i,j,k}$ 表示当前选取到第 $i$ 个数，选了 $j$ 个数，余数为 $k$，选取数的最大值。
边界：$dp_{0,0,0}=0$，$dp_{0,j,k}=- \inf(j>0 \vee k>0)$。
转移：
1. 当前不选，$dp_{i,j,k}=dp_{i-1,j,k}$。
2. 当前选，$dp_{i,j,k}=dp_{i-1,j-1,(k-a_i+K) \bmod \ K}+A_i$。
两者取最大值。
答案为 $dp_{n,K,X}$。
对于每个 $K$ 的情况做一次 dp，计算答案。
时间复杂度 $O(n^4)$，空间复杂度 $O(n^3)$，可以通过。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,a[N];
unsigned long long x,ans=1e18+1;
long long dp[N][N][N];
void DP(int K){
dp[0][0][0]=0;
for(int i=1;i<=n;i++)
for(int j=0;j<=i;j++)
for(int k=0;k<K;k++){
if(dp[i-1][j][k]!=-1)
dp[i][j][k]=dp[i-1][j][k];
if(j>0&&dp[i-1][j-1][(k-a[i]%K+K)%K]!=-1)
dp[i][j][k]=max(dp[i-1][j-1][(k-a[i]%K+K)%K]+a[i],dp[i][j][k]);
}
}
int main(){
cin>>n>>x;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++){
memset(dp,-1,sizeof(dp));
DP(i);
if(dp[n][i][x%i]!=-1)
ans=min(ans,(x-dp[n][i][x%i])/i);
}
cout<<ans;
return 0;
}
```