后三个点wa了,下载数据下来验证是对的啊
查看原帖
后三个点wa了,下载数据下来验证是对的啊
26418
pxpx楼主2023/9/26 23:49
#include <iostream>
#include <cmath>
using namespace std;
const int S_max = 1000;
int S;
int v[S_max + 1],f[S_max + 1];

int gcds(int i)
{
	int sum = 1;
	for(int j = 2; j < sqrt(i); j++)
	if(i % j == 0)
	sum += j + i/j;
	if(pow(sqrt(i),2) == i)
	sum += sqrt(i);
	return sum;
}

void init()
{
	v[0] = 0;
	for(int i = 2; i <= S; i++)
	v[i] = gcds(i);
	for(int i = 0; i <= S; i++)
	f[i] = 0;
}

void dp()
{
	for(int i = 1; i <= S ; i++)
	{
		int sum = 0;
		for(int j = i; j <= S; j++)
		sum += j;
		for(int j = S; j >= max(i, S - sum); j--)
		f[j] = max(f[j], f[j - i] + v[i]);
	}
}

int main()
{
	cin >> S;
	init();
	dp();
	cout << f[S];
	return 0;
}
2023/9/26 23:49
加载中...