😕/acm.hdu.edu.cn/showproblem.php?pid=4713 构造任意个数使得它们的和等于n并且它们的积最大。
#include<vector> #include<queue> #include<stdio.h> #include<map> #include<set> #include<string.h> #include<algorithm> #include<iostream> #include<math.h> #define mp make_pair using namespace std; typedef long long ll; const int mod = 1e9 + 7, inf = 0x3f3f3f3f; //const double pi = acos(-1.0); const ll INF = 0x3f3f3f3f3f3f3f3f; const int dx[4] = {0, 0, -1, 1}, dy[4] = {1, -1, 0, 0}; ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a % b);} ll quickpow(ll x, ll k) { ll res = 1; while(k){ if(k & 1) res = (res * x); k >>= 1, x = (x * x); } return res; } //ll C(int n, int m){return (fac[n] * quickpow((fac[m] * fac[n - m]) % mod, mod - 2)) % mod;} const int maxn = 1e4 + 10; double dp[maxn]; int prime[maxn]; vector<int> vi, fv[maxn]; void init() { for (int i = 2; i < maxn; ++i){ if (!prime[i]){ for (int j = 2; j * i < maxn; ++j) prime[j * i] = 1; } } for (int i = 2; i < maxn; ++i) if (!prime[i]) vi.push_back(i); for (int j = 0; j < vi.size(); ++j){ for (int i = maxn - 1; i >= vi[j]; --i){ int up = 1; while (up <= i){ if (dp[i - up] + log(up) > dp[i]){ fv[i] = fv[i - up]; fv[i].push_back(up); dp[i] = dp[i - up] + log(up); } up *= vi[j]; } } } } int ans[maxn]; void swa(int qi, int chang) { for (int i = qi; i < qi + chang - 1; ++i){ ans[i] = ans[i + 1]; } ans[qi + chang - 1] = qi; } int main() { init(); int t; scanf("%d", &t); while (t--){ int n; scanf("%d", &n); for (int i = 1; i <= n; ++i) ans[i] = i; int sum = accumulate(fv[n].begin(), fv[n].end(), 0); while (sum < n){ fv[n].push_back(1); ++sum; } sort(fv[n].begin(), fv[n].end()); int p = 1; for (int e : fv[n]){ swa(p, e); p += e; } for (int i = 1; i <= n; ++i) printf(i == n ? "%d\n" : "%d ", ans[i]); } return 0; }