P1249 最大乘积

  

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的做法,但实在做不下去了,就这样吧。贪心感觉还是很难想的,而且还很容易想错,还要好好学啊。高精度加法和乘法目前算是比较熟练了。最近几天练习模拟与高精度还算比较轻松的,基本上没有什么新的知识点,主要是细节比较多的模拟题有点恶心,但难度确实不大。加油!

上一篇:洛谷p2043质因子分解 入门 数论


下一篇:骏一创业孵化:用实际行动消灭人工智能鬼神论