让我们想一想，n划分成什么最优？

（首先一定要保证划分出来的数接近）

来暴搜枚举一下：

n=1:1=1
n=2:2=2
n=3:3=3
n=4:4=2*2
n=5:6=2*3
n=6:9=3*3
n=7:12=3*2*2
n=8:18=3*3*2
n=9:27=3*3*3
...... 

都是2或3呢~

所以得到贪心数学策略：取3取到n<3或n=4

进一步：

if(n%3==0)ans=pow(3,n/3);
if(n%3==1)ans=pow(3,n/3-1)*4
if(n%3==2)ans=pow(3,n/3)*2

所以有了30分代码：

#include<bits/stdc++.h>
using namespace std;
long long n;
long long ans;
int cmp;
inline long long read(){
    long long x=0,f=1;
    char c=getchar();
    if(c=='-')f=-1;
    else x=x*10+c-'0';
    c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}
int main(){
    n=read();
    if(n%3==0)ans=pow(3,n/3);
    if(n%3==1)ans=pow(3,n/3-1)*4;
    if(n%3==2)ans=pow(3,n/3)*2;
    long long aans=ans;
    while(aans)aans/=10,cmp++;
    cout<<cmp<<endl;
    cout<<ans;
    return 0;
}

？？？？ 方法错了？？？？

提示：在给定的范围内，最大乘积的位数不超过5000位。----by P4157[SCOI2006]整数划分

(眼瞎*1)

加高精~~

#include<bits/stdc++.h>
using namespace std;
long long n;
int a[5010];
void mul(int x){
    int q=0;
    for(int i=1;i<=a[0]+1;i++){
        a[i]=a[i]*x+q;
        q=a[i]/10;
        a[i]%=10;
    }
    if(a[a[0]+1])a[0]++;
}
inline long long read(){
    long long x=0,f=1;
    char c=getchar();
    if(c=='-')f=-1;
    else x=x*10+c-'0';
    c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}
int main(){
    cin>>n;
    a[0]=1,a[1]=1;
    if(n%3==0){
        for(int i=1;i<=n/3;i++)mul(3);
        cout<<a[0]<<endl;
        for(int i=a[0];i>=1;i--)cout<<a[i];
        return 0;
    }
    if(n%3==1){
        for(int i=1;i<=n/3-1;i++)mul(3);
        mul(4);
        cout<<a[0]<<endl;
        for(int i=a[0];i>=1;i--)cout<<a[i];
        return 0;
    }
    if(n%3==2){
        for(int i=1;i<=n/3;i++)mul(3);
        mul(2);
        cout<<a[0]<<endl;
        for(int i=a[0];i>=1;i--)cout<<a[i];
        return 0;
    }
    return 0;
}

50？？？

第2行输出最大乘积的前100位，如果不足100位，则按实际位数输出最大乘积。----by P4157[SCOI2006]整数划分

(眼瞎*2)

再抢救一下吧……

#include<bits/stdc++.h>
using namespace std;
long long n;
int a[5010];
void mul(int x){
    int q=0;
    for(int i=1;i<=a[0]+1;i++){
        a[i]=a[i]*x+q;
        q=a[i]/10;
        a[i]%=10;
    }
    if(a[a[0]+1])a[0]++;
}
inline long long read(){
    long long x=0,f=1;
    char c=getchar();
    if(c=='-')f=-1;
    else x=x*10+c-'0';
    c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}
int main(){
    cin>>n;
    a[0]=1,a[1]=1;
    if(n%3==0){
        for(int i=1;i<=n/3;i++)mul(3);
        cout<<a[0]<<endl;
        for(int i=a[0];i>=max(a[0]-99,1);i--)cout<<a[i];
        return 0;
    }
    if(n%3==1){
        for(int i=1;i<=n/3-1;i++)mul(3);
        mul(4);
        cout<<a[0]<<endl;
        for(int i=a[0];i>=max(a[0]-99,1);i--)cout<<a[i];
        return 0;
    }
    if(n%3==2){
        for(int i=1;i<=n/3;i++)mul(3);
        mul(2);
        cout<<a[0]<<endl;
        for(int i=a[0];i>=max(a[0]-99,1);i--)cout<<a[i];
        return 0;
    }
    return 0;
}

终于AC了