题目描述
提交记录
C. 选取整数
Problem ID: 7151
Contest ID: 5881
必做题
Runtime Error
题目描述
从 1 到 n 中选择若干个数，它们的总和不超过 n。 每个选择的数字都有自己的约数个数。
将这些数的约数个数相加，您可以得到一个总和。 找出这些所选数字的最大约数个数总和。
注意：这个总和不是那些选择的数字的总和，而是约数个数的总和。
输入样例
2
输出样例
2
数据约定
n<=1000
时间和空间约定
1s ，512M
#include <bits/stdc++.h>
#define maxn 400
#define maxm 2000
using namespace std;
int n,m;
int d[maxn];
int dp[maxn][maxm]={0};
int check(const int& x)
{
int ans=0;
for (int i=1;i*i<=x;i++)
if (x%i==0)
{
if (x/i!=i)
ans+=2;
else
ans++;
}
return ans;
}
void init()
{
cin>>n;
for (int i=1;i<=n;i++)
d[i]=i;
return;
}
void dpdo()
{
for (int j=d[1];j<=n;j++) dp[1][j]=check(d[1]);
for (int i=2;i<=n;i++)
for (int j=1;j<=n;j++)
{
dp[i][j]=dp[i-1][j];
if (j+d[i]>n)
dp[i][j]=max( dp[i-1][j-check(d[i])]+check(d[i]),dp[i][j]);
}
return;
}
void print()
{
cout<<dp[n][n];
return;
}
int main()
{
init();
dpdo();
print();
return 0;
}
RE0分