P1249 最大乘积 https://www.luogu.com.cn/problem/P1249
这道题套了一个高精度的皮,最核心的是贪心。我感觉贪心对我来说比较困难,很难想到。看了一下洛谷的题解,https://www.luogu.com.cn/blog/NKU-AI/solution-p1249 这篇写得非常全面,不过我还是不太确定这样贪心的正确性,确实这也很难证明,只能凭直觉推断...
所以我先写了一个暴力搜索,看看了规律,按照规律去对应一下上面的题解,发现确实是对的,于是就这么写下来了。
首先暴力的代码:用dfs直接搜索,写得还算比较顺(不枉我前段时间练了那么多的搜索...
#include <bits/stdc++.h> using namespace std; int n; int ans = 0,num = 1,vis[10010],vis1[10010]; void dfs(int k){ if(k==0){ if(num>ans){ ans = num; for(int i=1;i<=n;++i) vis1[i] = vis[i]; } return; } for(int i=1;i<=k;++i){ if(vis[i]==0){ vis[i] = 1; num *= i; dfs(k-i); vis[i] = 0; num /= i; } } } int main() { ios::sync_with_stdio(false); cin.tie(0); for(n=3;n<=50;++n){ memset(vis,0,sizeof(vis)); num = 1; ans = 0; dfs(n); cout<<n<<":"; for(int i=1;i<=n;++i){ if(vis1[i]==1){ cout<<i<<" "; } } cout<<endl; } return 0; }
这是结果,枚举了3-50,当然3和4的情况比较特殊,题目也说的不明确,就不管了
3:3 4:4 5:2 3 6:2 4 7:3 4 8:3 5 9:2 3 4 10:2 3 5 11:2 4 5 12:3 4 5 13:3 4 6 14:2 3 4 5 15:2 3 4 6 16:2 3 5 6 17:2 4 5 6 18:3 4 5 6 19:3 4 5 7 20:2 3 4 5 6 21:2 3 4 5 7 22:2 3 4 6 7 23:2 3 5 6 7 24:2 4 5 6 7 25:3 4 5 6 7 26:3 4 5 6 8 27:2 3 4 5 6 7 28:2 3 4 5 6 8 29:2 3 4 5 7 8 30:2 3 4 6 7 8 31:2 3 5 6 7 8 32:2 4 5 6 7 8 33:3 4 5 6 7 8 34:3 4 5 6 7 9 35:2 3 4 5 6 7 8 36:2 3 4 5 6 7 9 37:2 3 4 5 6 8 9 38:2 3 4 5 7 8 9 39:2 3 4 6 7 8 9 40:2 3 5 6 7 8 9 41:2 4 5 6 7 8 9 42:3 4 5 6 7 8 9 46:2 3 4 5 6 7 9 10 47:2 3 4 5 6 8 9 10 48:2 3 4 5 7 8 9 10 49:2 3 4 6 7 8 9 10 50:2 3 5 6 7 8 9 10
可以很明显的看出规律,就是从2递增的一个序列,中间去掉了一个元素。
不过还有特殊的情况,具体以2021这个n为例(参考洛谷题解)
以2021为例,由于把2021分拆成若干个互不相等的自然数的和的分法只有有限种,因而一定存在一种分法,使得这些自然数的乘积最大。(存在性)
若1作因数,则显然乘积不会最大。把2021分拆成若干个互不相等的自然数的和,因数个数越多,乘积越大。为了使因数个数尽可能地多,我们把2004分成2+3…+n直到和,设这个和为s,直到s>=2021,设k=s-2021。
若k==1,则因数个数至少减少1个,为了使乘积最大,应去掉最小的2,并将最后一个数(最大)加上1。
e.g. 如n=8时,由于s=2+3+4=9,k=9-8=1,所以去掉最小的2,并让4+1,故8=3+5
若k>1,则去掉等于k的那个数,便可使乘积最大。
e.g.如n=10时,由于s=2+3+4+5=14,k=14-10=4,所以去掉4,故10=2+3+5
这样思路就很明确的,可以很轻松地写出拆分的代码,最后再用高精度乘法即可。
#include <bits/stdc++.h> using namespace std; int vis[10010],num[10010]; void muti(int k){ int jw=0; for(int i=0;i<10000;++i){ num[i] = num[i]*k+jw; jw = num[i] / 10; num[i] %= 10; } } void print(){ bool isbeg = false; for(int i=9999;i>=0;--i){ if(!isbeg){ if(num[i]!=0){ isbeg = true; cout<<num[i]; } } else{ cout<<num[i]; } } cout<<endl; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n,i; cin>>n; int sum = 0; for(i=2;sum<n;++i){ sum += i; vis[i] = 1; } if(sum==n+1){ vis[2] = 0; vis[i] = 1; vis[i-1] = 0; } else if(sum>n+1){ vis[sum-n] = 0; } bool isbeg = false; num[0] = 1; for(int i=1;i<=n;++i){ if(vis[i]==1){ if(!isbeg){ isbeg = true; cout<<i; muti(i); } else{ cout<<" "<<i; muti(i); } } } cout<<endl; print(); return 0; }
小结:这道题还有用dp的做法,但实在做不下去了,就这样吧。贪心感觉还是很难想的,而且还很容易想错,还要好好学啊。高精度加法和乘法目前算是比较熟练了。最近几天练习模拟与高精度还算比较轻松的,基本上没有什么新的知识点,主要是细节比较多的模拟题有点恶心,但难度确实不大。加油!