题解：AT_abc192_f [ABC192F] Potion

题意

在

N

个数里选取任意个数，设个数为

K

，求

\frac{X-\sum A_i}{K}

最小值。

思路

首先可以发现所有数的总和不会超过

X

。

N

范围较小，考虑枚举选取个数。

设个数为

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)

。

转移：

当前不选， $dp_{i,j,k}=dp_{i-1,j,k}$ 。
当前选， $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;
}

题解：AT_abc192_f [ABC192F] Potion

文章操作

题意

思路

相关推荐

评论

题解：AT_abc192_f [ABC192F] Potion