洛谷 P1018 [NOIP2000 提高组] 乘积最大

题目地址

一个DP问题 有人也用搜索解决 但是我感觉不好优化
如果不优化 应该会超时吧

我也不确定我的DP方式对不对 反正AC了
(也有可能我的DP方法不对,洛谷的测试数据太弱了)

先搜索找出最优的把N分割成2个数乘积最大的方式
再在这个基础上搜索把N分割成3个数乘积最大的方式
一直下去到把N分割成K+1个数乘积最大的方式

这道题处理大数相乘也是个麻烦事

数学理论
把N分割成2个数的话
1 保证是首位最大的方式
2 2个数的差最小 那么这就是最优的方式

对于把N分割成多个数第一条肯定是必须满足的
第二条怎么计算我也不知道 所以还是大数相乘对比结果

#include <stdio.h>
#include <string.h>

// const int maxWidth=40;


//大数乘法
//传入数组是倒叙 返回也是倒叙
void mul(int * array1,int len1,int* array2,int len2,int *result,int &len)
{
    //将结果储存在 resullt中，result[i + j] = a[i] * b[j]是关键算法 
    int i,j;
    for(i = 0; i < (len1+len2); i++)
    {
        result[i]=0;
    }
    for(i = 0; i < len1; i++)
    {
        for(j = 0; j < len2; j++)
        {
            result[i + j] += array1[i] * array2[j];
        }
    }

    //从低位到高位进行进位
    for(i = 0; i < (len1+len2); i++)
    {
        if(result[i] > 9)
        {
            result[i+1] += result[i]/10;
            result[i] %= 10; 
        }
    }

    //将前导0全部剔掉，比如我们结果是236，在result中
    //是这样存储的63200……我们需要定位到第一个不为零的数，它的位置也就是i ，两数相乘，位数最多是两数位数之和
    for(i = len1 + len2-1; i >= 0 ; i--)
    {
        if(result[i] != 0) 
        {
            break;
        }
    }
    len=i+1;

}
//大数对比 array1>array2 返回1 array1=array2 返回0 否则返回-1
int compare(int * array1,int len1,int* array2,int len2){
    if(len1>len2)
    {
        return 1;
    }
    else if(len1<len2)
    {
        return -1;
    }

    for(int i=len1-1;i>=0;i--)
    {
        if(array1[i]>array2[i])
        {
            return 1;
        }
        else if(array1[i]<array2[i])
        {
            return -1;
        }
    }
    return 0;
}

int fenge(char* a,int n,int * bj,int **array,int*array_len)
{
    int i=0,j=0,k=0;
    array_len[0]=0;
    for(i=0;i<n;i++)
    {
        if(bj[i]==1)
        {
            k++;
            array_len[k]=0;
            j=0;
        }
        array[k][j]=a[n-i-1]-'0';
        array_len[k]++;
        j++;
    }
    k++;
    return k;
}

void printNum(int * array,int len){
    for(int i=len-1; i >=0; i--)
    {
        printf("%d",array[i]);
    }
    printf("\n");
}

void printArray(int ** array,int *arrayLen,int len){
    for(int i=0; i <len; i++)
    {
        printNum(array[i],arrayLen[i]);
    }
}



int main(){
    // char a[50],b[50];
    // scanf("%s %s",&a,&b);
    // int len1=strlen(a);
    // int len2=strlen(b);
    // int* array1=new int[len1];
    // int* array2=new int[len2];
    // int i;
    // for(i=0;i<len1;i++)
    // {
    //     array1[len1-i-1]=a[i]-'0';
    // }
    // for(i=0;i<len2;i++)
    // {
    //     array2[len2-i-1]=b[i]-'0';
    // }
    // int len=0;
    // int* result=new int[len1+len2];
    // mul(array1,len1,array2,len2,result,len);
    


    // //接着i继续输出，就是我们的结果 

    // for(i=len-1; i >=0; i--)
    // {
    //     printf("%d",result[i]);
    // }
    // delete result;

    char a[40];
    int n,k;

    scanf("%d %d",&n,&k);
    scanf("%s",&a);
    int i,j,l;
    //分割后的数组
    int **array=new int*[k+1];
    //分割后的数组长度
    int *array_len=new int[k+1];
    for(i=0;i<=k;i++)
    {
        array[i]=new int[n];
        array_len[i]=0;
    }
    
    //分割位置的标记
    int* bj=new int[n];
    for(i=0;i<n;i++)
    {
        bj[i]=0;
    }

    int* maxResult=new int[n];
    int  maxlen=0;
    int  maxIndex=0;

    int* tmpResult=new int[n];
    int tmplen=0;
    int* tmpResult2=new int[n];
    int tmplen2=0;

    for(i=1;i<=k;i++)
    {
        maxIndex=-1;
        for(j=1;j<n;j++)
        {
            if(bj[j])
            {
                continue;
            }
            else{
                bj[j]=1;
                //分割字符串
                int tmp_Array_len=fenge(a,n,bj,array,array_len);

                // printArray(array,array_len,tmp_Array_len);
                //连乘
                mul(array[0],array_len[0],array[1],array_len[1],tmpResult,tmplen);
                for(l=2;l<tmp_Array_len;l++)
                {
                    mul(tmpResult,tmplen,array[l],array_len[l],tmpResult2,tmplen2);
                    tmplen=tmplen2;

                    int* tmpResult3=tmpResult;
                    tmpResult=tmpResult2;
                    tmpResult2=tmpResult3;
                }

                // printf("mul result:\n");
                // printNum(tmpResult,tmplen);
                // printf("\n");

                //对比
                if(maxIndex<0||compare(maxResult,maxlen,tmpResult,tmplen)<0)
                {
                    maxIndex=j;

                    maxlen=tmplen;
                    int* tmpResult3=maxResult;
                    maxResult=tmpResult;
                    tmpResult=tmpResult3;
                }
               
                bj[j]=0;
                
            }
            
        }

        if(maxIndex>=0)
        {
            // printf("max result:\n");
            // printNum(tmpResult,tmplen);
            // printf("\n");

            bj[maxIndex]=1;
        }
        
    }

    
    printNum(maxResult,maxlen);

    for(i=0;i<=k;i++)
    {
        delete array[i];
    }
    delete array;
    delete array_len;
    delete bj;
    delete maxResult;
    delete tmpResult;
    delete tmpResult2;
    return 0;
}