AcWing 1234. 倍数问题 朴素DP与背包优化
原题链接
中等
作者:
Snrise
,
2024-04-04 12:58:23
,
所有人可见
,
阅读 2
朴素D P
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define endl '\n'
#define int long long
using namespace std;
const int N = 1010;
const int K = 110;
int f[N][5][K];
int mod, n;
int get_mod(int a, int b)
{
return (a % b + b) % b;
}
signed main(void)
{
std::ios::sync_with_stdio(false);
cin >> n >> mod;
memset(f, -0x3f, sizeof(f));
for (int i = 0; i <= n; i++)
{
f[i][0][0] = 0;
}
for (int i = 1; i <= n; i++)
{
int w;
cin >> w;
for (int j = 1; j <= 3; j++)
{
for (int k = 0; k < mod; k++)
{
f[i][j][k] = max(f[i - 1][j][k], f[i - 1][j - 1][get_mod(k - w, mod)] + w);
}
}
}
cout << f[n][3][0] << endl;
return 0;
}
贪心优化:
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define endl '\n'
#define int long long
using namespace std;
const int K = 1010;
int f[5][K];
vector<int> g[K];
int mod, n;
int get_mod(int a, int b)
{
return (a % b + b) % b;
}
signed main(void)
{
std::ios::sync_with_stdio(false);
cin >> n >> mod;
for (int i = 0; i < n; i++)
{
int w;
cin >> w;
g[w % mod].push_back(w);
}
memset(f, -0x3f, sizeof(f));
f[0][0] = 0;
for (int i = 0; i < mod; i++)
{
sort(g[i].begin(), g[i].end(), greater<int>());
for (int u = 0; u < 3 && u < g[i].size(); u++)
{
int w = g[i][u];
for (int j = 3; j >= 1; j--)
{
for (int k = 0; k < mod; k++)
{
f[j][k] = max(f[j][k], f[j - 1][get_mod(k - w, mod)] + w);
}
}
}
}
cout << f[3][0] << endl;
return 0;
}