AcWing 1047. 糖果
原题链接
简单
作者:
y总的小迷弟
,
2023-10-08 10:33:32
,
所有人可见
,
阅读 68
//考虑设f[i][j]表示选前i个物品,总个数mod k等于j的集合;
//不难写出方程: f[i][j] = max(f[i - 1][j], f[i - 1][j - a[i]] + a[i]);
//但考虑到j-a[i]可能为负,最常见的处理方式是加一个偏移量,但这题会爆空间;
//结合取模的性质,不难有:((j - a[i]) % k + k) % k;
//其余细节见代码
#include<bits/stdc++.h>
using namespace std;
int n, k;
int a[110];
int f[110][110];
int main()
{
cin >> n >> k;
for(int i = 1;i <= n;i++)
cin >> a[i];
for(int i = 1;i < k;i++)
f[0][i] = -0x3f3f3f3f;//不合法状态,在本题中队答案正确性有影响;
f[0][0] = 0;
for(int i = 1;i <= n;i++)
{
for(int j = 0;j <= k - 1;j++)//模k必然在这个范围内
{
f[i][j] = max(f[i - 1][j], f[i - 1][((j - a[i]) % k + k) % k] + a[i]);
}
}
cout << f[n][0] << endl;
return 0;
}
很好奇珂迷说的蓝书是什么书qwq
蓝书不是算法竞赛进阶指南吗?
啊?那白书呢?
原来你还活着(