题目描述

选取和不超过S（S<=1000）的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。

输入格式

输入一个正整数S。

输出格式

输出最大的约数之和。

输入输出样例

输入 #1复制

11

输出 #1复制

9

思路：将1000以内的每个数的最大约数和用一个数组F存起来（类似于01背包问题的价值），然后定义数组dp[i][j]，i表示前i个数的最优解（每个数加起来和不大于i，且约数和最大），直接dp求解。

附AC代码

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{int F[1001];short int dp[1001][1001];//注意，用int型内存会溢出 memset(F,0,sizeof(F));memset(dp,0,sizeof(dp));int n;cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<i;j++)if(i%j==0)F[i]+=j;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)if(j<i)dp[i][j]=dp[i-1][j];else dp[i][j]=max((int)dp[i-1][j],dp[i-1][j-i]+F[i]);}
//	for(int i=1;i<=n;i++)
//	{
//		cout<<endl;
//		for(int j=1;j<=n;j++)
//		cout<<dp[i][j]<<" "; 
//	}cout<<dp[n][n]<<endl;return 0;}