注意:本题情况特殊,所以用一维数组记录方案不会出错,不是通法,原因待查!!!
背包法,只优化了空间,由于在O(N*N)复杂度之上还要乘以高精度计算耗时,所以TLE
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=10010;
int n;
vector<int> f[N];
int back[N];
vector<int> mul(vector<int> &a,int b){
vector<int> c;
int t=0;
for(int i=0;i<a.size() || t;i++){
if(i<a.size())t+=a[i]*b;
c.push_back(t%10);
t/=10;
}
while(c.size()>1 && c.back()==0)c.pop_back();
return c;
}
bool cmp(vector<int> &a,vector<int> &b){
if(a.size()!=b.size())return a.size()>b.size();
for(int i=a.size()-1;i>=0;i--){
if(a[i]!=b[i])return a[i]>b[i];
}
return false;
}
int main(){
cin>>n;
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
f[0].push_back(1);
for(int i=1;i<=n;i++)f[i].push_back(0);
vector<int> items;
vector<int> temp;
for(int i=1;i<=n;i++){
for(int j=n;j>=i;j--){
temp=mul(f[j-i],i);
if(cmp(temp,f[j])){
f[j]=temp;
back[j]=j-i;
}
}
}
for(int t=n;t;t=back[t]){
items.push_back(t-back[t]);
}
reverse(items.begin(),items.end());
for(auto t:items)cout<<t<<' ';
auto &t=f[n];
cout<<'\n';
for(int i=t.size()-1;i>=0;i--)cout<<t[i];
return 0;
}
优化掉高精度计算耗时,先对数化找最大方案,最后求结果,相当巧妙,可以AC
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=10010;
int n;
double f[N],w[N];
int back[N];
vector<int> mul(vector<int> &a,int b){
vector<int> c;
int t=0;
for(int i=0;i<a.size() || t;i++){
if(i<a.size())t+=a[i]*b;
c.push_back(t%10);
t/=10;
}
while(c.size()>1 && c.back()==0)c.pop_back();
return c;
}
int main(){
cin>>n;
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for(int i=1;i<=n;i++)f[i]=-2e9;//恰好问题的初始化
f[0]=0;
vector<int> items;
for(int i=1;i<=n;i++)w[i]= log(i);//利用对数计算性质,lna+lnb=ln(a*b)
for(int i=1;i<=n;i++){
for(int j=n;j>=i;j--){
if(f[j]<f[j-i]+w[i]){
f[j]=f[j-i]+w[i];
back[j]=j-i;
}
}
}
for(int t=n;t;t=back[t]){
items.push_back(t-back[t]);
}
reverse(items.begin(),items.end());
vector<int> ans(1,1);
for(auto &t:items){
cout<<t<<' ';
ans=mul(ans,t);
}
cout<<'\n';
for(int i=ans.size()-1;i>=0;i--)cout<<ans[i];
return 0;
}
打表找规律后,分组二分
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=10010;
int n;
int a[N+2];
int get_a(int x){
return (x+1)*(x+4)/2;
}
vector<int> mul(vector<int> &a,int b){
vector<int> c;
int t=0;
for(int i=0;i<a.size() || t;i++){
if(i<a.size())t+=a[i]*b;
c.push_back(t%10);
t/=10;
}
while(c.size()>1 && c.back()==0)c.pop_back();
return c;
}
int main(){
cin>>n;
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(n==4 || n==3){
cout<<n<<'\n'<<n;
return 0;
}//第i组的n范围是[a[i],a[i+1]-1]
int l=1,r=1500;
while(l<r){
int mid=l+r+1>>1;
if(get_a(mid)<=n)l=mid;
else r=mid-1;
}
int group=r;
int bound= get_a(group);
int seq=n-bound;
for(int i=2;i<=group+2;i++)a[i]=i;
if(n== get_a(group+1)-1){
for(int i=2;i<=group+2;i++)a[i]++;
a[group+2]++;
}
else {
int pos=group+2;
int t=seq;
while(t--)a[pos--]++;
}
for(int i=2;i<=group+2;i++)cout<<a[i]<<' ';
cout<<'\n';
vector<int>ans(1,1);
for(int i=2;i<=group+2;i++)ans=mul(ans,a[i]);
for(int i=ans.size()-1;i>=0;i--)cout<<ans[i];
return 0;
}
贪心分析过程(很难直接想到,只有打表找规律后才能利用贪心分析证明前面打表发现的规律适用于全体正整数n)
1.如果c=a+b<=a*b,即1/a+1/b<=1,而a,b其中不包含1时不等式一定成立,
所以当能拆出两个大于1的合法的因子时,拆开一定不会变差
2.所以考虑当2开始,{2,3,4,...}这样枚举,拆得到的组数一定是最多的,
但是最后一次拆分可能(考虑余数是0)同时会得到一个之前枚举过的不能再存在的数,那么放弃最后一次拆分最优吗?(易错点,很坑)
3.答案是并不是,因为最后一次拆分一定只能得到一个合法的数,
可以这样考虑,另一个不合法的数相当于是余数,求最优解就是在于证明把这部分加到已经枚举那部分数上
而且不管怎么加组数是不变的,所以不能用第1条性质来判断是不是最优解
(即2中放弃最后一次拆分相当于余数加在最后一次枚举的合法的数上,仅凭前面的条件不能判断这么做是最优的)
4.先考虑加1个数,发现只能加在排好后的最后一个数字上
5.再加一个数,发现加在倒数第二个数上比加在最后一个数字是更好
6.后面依次考虑......当余数达到当前已经存在的组成员数+2时,可以给组扩容,
即新添加一个从2开始依次从小到大枚举的成员,这样根据性质1,一定比把余数加在其他数上好
7.贪心合理性证明完毕