P1734 最大约数和
基本思路
设状态方程F[i][j]为前\(i\)个数和为\(j\)时的最大约数和。
状态转移则是F[i][j] = max(F[i - 1][j], F[i - 1][j - i] + divisorSum(i)
即要么选\(i\)，要么不选。
代码实现
WA一个点，TLE六个点
\(30ptsCode\)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int S, ans = 0;
int F[1010][1010];
int getCd(int n)
{
int sum = 0;
for (int i = 1; i < n; i++)
{
if (n % i == 0)
{
sum += i;
}
}
return sum;
}
int main()
{
cin >> S;
for (int i = 1; i <= S; i++)
{
for (int j = 1; j <= i * (1 + i) / 2; j++)
{
if (j >= i)
{
F[i][j] = max(F[i][j], F[i - 1][j - i] + getCd(i));
if (j <= S)
ans = max(ans, F[i][j]);
}
else
{
F[i][j] = F[i - 1][j];
}
}
}
cout << ans;
return 0;
}
我觉得我思路是可行的，只好从代码实现上找问题。
首先for (int j = 1; j <= i * (1 + i) / 2; j++)是让我TLE的关键，我想改它。
然后我看了一眼题目，发现我犯了一个很严重的错误。\(S\)指的是选取若干个数的和，而不是指从\(1 \sim S\)中选若干个数！
所以我转移方程的第二维直接枚举到\(S\)即可。
解决了TLE问题。
然后就是第二个关键点，已经屡次犯错了，在写二维背包时，总是搞错\(F[i][j] = F[i - 1][j]\)的次序，从而导致很多情况下根本没让\(F[i - 1][j]\)参与状态转移。比如说该题又莫名写成了把\(F[i - 1][j]\)放在只有\(j < i\)时才进行转移。这显然是不对的。
正确的写法应是每一次都考虑\(F[i - 1][j]\)，然后看情况考虑\(F[i -1][j - v[i]] + w[i]\).
for (int j = 1; j <= i * (1 + i) / 2; j++)
{
F[i][j] = F[i - 1][j];
if (j >= i)
{
F[i][j] = max(F[i][j], F[i - 1][j - i] + getCd(i));
}
}
最终AC
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int S, ans = 0;
int F[1010][1010];
int getCd(int n)
{
int sum = 0;
for (int i = 1; i < n; i++)
{
if (n % i == 0)
{
sum += i;
}
}
return sum;
}
int main()
{
cin >> S;
for (int i = 1; i <= S; i++)
{
for (int j = 1; j <= S; j++)
{
F[i][j] = F[i - 1][j];
if (j >= i)
{
F[i][j] = max(F[i][j], F[i - 1][j - i] + getCd(i));
}
}
}
cout << F[S][S];
return 0;
}
优化空间
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int S, ans = 0;
int F[1010];
int getCd(int n)
{
int sum = 0;
for (int i = 1; i < n; i++)
{
if (n % i == 0)
{
sum += i;
}
}
return sum;
}
int main()
{
cin >> S;
for (int i = 1; i <= S; i++)
{
for (int j = S; j >= i; j--)
{
F[j] = max(F[j], F[j - i] + getCd(i));
}
}
cout << F[S];
return 0;
}