上传到服务器的网站打开是空白,免费单页网站在线制作,柳市做网站制作,如何制作网站平台P1734 最大约数和 - 洛谷 | 计算机科学教育新生态
题目描述
选取和不超过 S 的若干个不同的正整数#xff0c;使得所有数的约数#xff08;不含它本身#xff09;之和最大。
输入格式
输入一个正整数 S。
输出格式
输出最大的约数之和。
输入输出样例
输入 #1复制
…P1734 最大约数和 - 洛谷 | 计算机科学教育新生态
题目描述
选取和不超过 S 的若干个不同的正整数使得所有数的约数不含它本身之和最大。
输入格式
输入一个正整数 S。
输出格式
输出最大的约数之和。
输入输出样例
输入 #1复制
11
输出 #1复制
9
说明/提示
【样例说明】
取数字 4 和 6可以得到最大值 (12)(123)9。
【数据规模】
对于 100% 的数据1≤S≤1000。
思路
题目的意思是选取诺干个数这些数之和小于n求出这些数的约数最大和。
我们预处理把每个数的约数写出来。然后就是背包问题了。
注意只有dp会满分
代码如下
暴力
#include iostream
#includealgorithm
#includestring
using namespace std;
typedef long long ll;
const ll N 2001;
ll cnt[N];
ll num[N];
ll n;
int is_number(ll x)
{int sum 0;for(ll i 1 ; i x ; i){if(x % i 0)sum i;}return sum;
}
ll dfs(ll x,ll sp)
{if(x n-1)return 0;if(sp num[x])return max(dfs(x1,sp-num[x])cnt[x],dfs(x1,sp));elsereturn dfs(x1,sp);}int main()
{cin n;for(ll i 1 ; i n-1 ; i){cnt[i] is_number(i);//求出1~n-1的各个约数之和
// cout i 的约数之和: arr[i] endl;num[i] i; }cout dfs(1,n);return 0;}
记忆化搜索
#include iostream
#includealgorithm
#includestring
using namespace std;
typedef long long ll;
const ll N 2001;
ll cnt[N];
ll num[N];
ll n;
ll mem[N][N];
int is_number(ll x)
{int sum 0;for(ll i 1 ; i x ; i){if(x % i 0)sum i;}return sum;
}
ll dfs(ll x,ll sp)
{ll sum -1e9;if(mem[x][sp])return mem[x][sp];if(sp 0)return 0;if(x n-1)return 0;if(sp num[x])sum max(dfs(x1,sp-num[x]) cnt[x],dfs(x1,sp));elsesum dfs(x1,sp);mem[x][sp] sum;return sum;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin n;for(ll i 1 ; i n ; i){cnt[i] is_number(i);//求出1~n-1的各个约数之和
// cout i 的约数之和: arr[i] endl;num[i] i; }cout dfs(1,n);return 0;}
dp
#include iostream
#includealgorithm
#includestring
using namespace std;
typedef long long ll;
const ll N 2001;
ll cnt[N];
ll num[N];
ll n;
ll f[N][N];
int is_number(ll x)
{int sum 0;for(ll i 1 ; i x ; i){if(x % i 0)sum i;}return sum;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin n;for(ll i 1 ; i n ; i){cnt[i] is_number(i);//求出1~n-1的各个约数之和
// cout i 的约数之和: arr[i] endl;num[i] i; }for(ll i n-1 ; i 1 ; i--){for(ll j 0 ; j n ; j){if(j num[i])f[i][j] max(f[i1][j-num[i]] cnt[i],f[i1][j]);elsef[i][j] f[i1][j]; } }cout f[1][n];return 0;}
