AcWing 1234. 倍数问题
$\text{贴一下常规做法,不过会}TLE+MLE\text{。不过具有}dp\text{的普适性。}$
1.定义状态
$dp(i,j,k)\text{ 前}i\text{个物品选}j\text{个总和}\%k\text{的最大值。}$
2.初始化( 极其重要 )
$\text{前}i\text{个数选0个模}k\text{的最大值都为0,其他都应该是负无穷,因为选0个数总和只能为0。}$
$\text{而没选物品的总和为}0\%k\text{不可能为其他值。}$
3.状态转移
$\text{对第}\mathrm{i}\text{个物品选与不选进行状态转移}:$
$dp(i,j,k)=max(dp(i-1,j,k),dp(i-1,j-1,(k-a[i])\%k))$
本题目的$dp$思维导图
对于余数处理的推导
y总评论区详细解释
优化版本分析
分析
组合问题的最优解问题
在一类物品中,选取物品进行组合,使得满足某个条件的最优解
实际上是背包问题。
$$\text{闫氏}DP\text{分析法}$$
状态表示:$f[i][j][k]:$所有从$i$件物品中,选了$j$件物品且总和$%K$的余数为$k$的集合
属性:$Max$
状态计算:
划分–>找不同点–>选或不选第i个数
(1)不选第$i$个物品
$f[i][j][k]=f[i-1][j][k]$
(2)选第$i$个物品
$f[i][j][j]=f[i-1][j-1][(k-a[i])%k]$
时间复杂度:$O$($10^{5}$$\times$$4$$\times$$1000$$)$$=$$O$($4$$\times$$10^{8}$$)$;
超过$10^8$,会$TLE$。
发现只需考虑$k$的数值,与$3$个数的和值无关。
我们要找到的是$3$个数$mod k$的最大值
余数$k$为$1000,$对于每种$k,$只需保留最大的那$3$位数。
总共最多只需保留$3000$个数
$4$$\times3000$$\times$$k$$=$$1.2$$\times$$10^{7}$
优化后时间复杂度:$O$$(10^{7})$
参考资源: 参考的这个大佬的优化背包问题的题解
朴素未被优化的本题目代码实现
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
int n, K, a[N];
int main(void){
cin >> n >> K;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>> (4, vector<int> (K, -2e9)));
for (int i = 0; i <= n; i++) dp[i][0][0] = 0;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= 3; j++){
for (int k = 0; k < K; k++){
dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - 1][((k - a[i]) % K + K) % K] + a[i]);
}
}
// printf("%d %d %d\n", dp[i][1][0], dp[i][2][0], dp[i][3][0]);
}
cout << dp[n][3][0];
return 0;
}
作者:Mamba_ZJP
链接:https://www.acwing.com/solution/content/21422/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
优化版本代码实现
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
// C++ 的取模正数是正数,负数是负数,
//而真正意义上的取模符号结果都是正的比如 -1 % 2 用C++的结果是-1而实际真正的结果是1,(数学上模的结果都是正的)
//所以会看到 (____ % k + k ) % k 解决上面的问题 比如-5 % 3 = 1;
//而C++中-5 % 3 的结果是 -2 ,我们通过 ((-5 % 3) + 3) % 3 = 1 ;这样就得到真正的结果
using namespace std;
// #define N 100010
// int a[N];
// int f[100001][3][1001];
#define N 1010
vector<int> a[N];
int f[4][N];
int main()
{
//背包去做,前面一维是i个物品,后面几维就是限制,一个限制一维,一般的只有体积只加一维
//这里有两个限制,一个是三个数,一个是k的倍数
//从i个数中选,且已经选了j个数,且总和模KK的余数是k的选法 的集合
//优化:由于 ( a + b + c ) % k,
//我们不需要管abc本身,只需要考虑他们的余数就可以了,我们最后取最大的数的余数即可
//这样我们把10^5个数对K取模, 结果就在0~k的取值中间,所以我们把10^5压缩到了 3000(3*1000),1000是k的取值范围
// for(int i = 0; i <=n;i++)
// {
// for(int j = 1; j <=3 ;j++)//个数
// {
// for(int k = 0; k <KK;k++) //当前模以k 的余数
// {
// f[i][j][k] = f[i-1][j][k];//不选
// //选的话,就是从i-1中选,前面选了j-1个数,
// //(前面选的数+ a[i] ) % K = k ---> 前面选的数 = ( k - a[i] )%K
// f[i][j][k] = max( f[i][j][k], f[i-1][j-1][ ( ( k - a[i] )%KK + KK )% KK] + a[i]);
// }
// }
// }
int n,m;
cin >> n >> m;
for (int i = 0; i < n; i ++ )
{
int x;
scanf("%d", &x);
a[x % m].push_back(x); //每个数的余数存到一个二维数组里面
}
memset(f, -0x3f, sizeof f);
f[0][0] = 0;
for (int i = 0; i < m; i ++ )
{
sort(a[i].begin(), a[i].end());
reverse(a[i].begin(), a[i].end());
//选三个数这里没有太懂,就是每个余数中选三个最大的,
//想了一下:刚好有可能三个最大数都是 这个余数的三个数相加
for (int u = 0; u < 3 && u < a[i].size(); u ++ )
{
int x = a[i][u];
for (int j = 3; j >= 1; j -- )
for (int k = 0; k < m; k ++ )
f[j][k] = max(f[j][k], f[j - 1][((k - x) % m + m) % m] + x);
}
}
cout << f[3][0];
return 0;
}