思路求证伪

回复帖子

@expect  2020-01-10 19:49 回复

要求将一个整数 $n$ 划分为若干个正整数,使得这些正整数乘积最大。

考虑简化问题,将其划分为两个整数。

由基本不等式得, $x \times y \le \frac{n^2}{4}$

对 $x$ 和 $y$ 递归做上述过程。

核心代码:

Int dfs(int x){
    if(x<=3){
        Int res;
        if(x==2) res=2;
        else if(x==3) res=3;
        return res;
    }
    if(memery[x]!=0) return memery[x];
    if(x&1) memery[x]=dfs(x/2)*dfs(x/2+1);
    else memery[x]=dfs(x/2),memery[x]=memery[x]*memery[x];
    return memery[x];
}

Int 为封装的高精类型。

x=14。

按你的思路,应该是分成7+7,然后递归求解。7求出来应该是12,然后12x12=144。

实际上应该分出来3,3,3,3,2,答案是162。

证伪只需要一个反例。证毕。

讲道理吧。你不能保证分出来的结果一定能被分成两个x/2,还有跨两半的情况。

我把Int换成long long了之后试了一下。的确是输出144的。

您的代码(加了点东西) memery拼错了,应该是memory,不知道有意无意

#include <bits/stdc++.h>
using namespace std;
#define int long long 
int memery[100000+100];
int dfs(int x){
    if(x<=3){
        int res;
        if(x==2) res=2;
        else if(x==3) res=3;
        return res;
    }
    if(memery[x]!=0) return memery[x];
    if(x&1) memery[x]=dfs(x/2)*dfs(x/2+1);
    else memery[x]=dfs(x/2),memery[x]=memery[x]*memery[x];
    return memery[x];
}
#undef int //long long 
int main()
{
    cout<<dfs(14)<<endl;
}

但我的标程(大号LightningUZ的代码)告诉我答案的确是162。

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。