[Acwing|蓝桥杯] 1234. 倍数问题 背包dp+优化

前言

传送门 :

思路

看完题目之后大概就知道是 动态规划了

状态表示 : d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]从前 i i i个数中选 j j j个总和正好是 k k k的最大值

因为要求的是 k k k的倍数,所以我们对第三层取 % \% % ,即总和正好是 % k \%k %k的最大值

状态计算 : d p [ i ] [ j ] [ k ] = m a x ( d p [ i − 1 ] [ j ] [ k ] , d p [ i − 1 ] [ j − 1 ] [ ( ( k − a [ i ] ) % K + K ) % K ] + a [ i ] dp[i][j][k] = max(dp[i-1][j][k],dp[i-1][j-1][((k-a[i])\%K+K)\%K] + a[i] dp[i][j][k]=max(dp[i−1][j][k],dp[i−1][j−1][((k−a[i])%K+K)%K]+a[i])

( ( k − a [ i ] % K ) + K ) % K ((k-a[i]\%K)+K)\%K ((k−a[i]%K)+K)%K这一个是将负数取模转正,很常用了属于是

但是如果这么搞上去,会 M L E MLE MLE, 1 e 5 ∗ 1 e 3 ∗ 3 1e5*1e3*3 1e5∗1e3∗3,(题解的那个 v e c t o r vector vector也 M L E MLE MLE了)

因此我们考虑同背包问题一样优化第一维

因此状态转移变为 : 只不过第二维度的循环需要倒序 d p [ j ] [ k ] = m a x ( d p [ j ] [ k ] , d p [ j − 1 ] [ ( ( k − a [ i ] ) % K + K ) % K ] + a [ i ] dp[j][k] = max(dp[j][k],dp[j-1][((k-a[i])\%K+K)\%K] + a[i] dp[j][k]=max(dp[j][k],dp[j−1][((k−a[i])%K+K)%K]+a[i])

但是处理完 M L E MLE MLE之后,又会遇到 T L E TLE TLE的问题

因为我们是,三层循环的进行转移 O ( N ∗ K ) O(N*K) O(N∗K)

for(int i=1;i=1;j--)
		for(int k=0;k>n>>K;
	for(int i=1;i>a[i];
		allr[a[i]%K].pb(a[i]);
	}

	memset(f,-0x3f,sizeof f);
	f[0][0] = 0 ;

	for(int i=0;i