LG1018 乘积最大

2019-04-14 19:51:01


这道题很简单,我们先写个DP:

#include<cstdio>//头文件
using namespace std;

long long a[11][11],f[11][11];
long long s;
int n,i,j,k,k1;

int max(int a, int b){
    return a>b?a:b;
}

int main(){
    scanf("%d%d",&n,&k1);
    scanf("%lld",&s);
    for(i=n; i >=1 ;i--){
        a[i][i]=s%10;
        s/=10;
    }

    for(i=2; i<=n;i++)
        for(j=i-1;j>=1;j--)
            a[j][i]=a[j][i-1]*10+a[i][i];
    for(i=1; i<=n; i++)
        f[i][0]=a[1][i];

    for(k=1; k<=k1; k++)
        for(i=k+1; i<=n; i++)
            for(j=k; j<i;j++)
                f[i][k] = max(f[i][k],f[j][k-1]*a[j+1][i]);

    printf("%lld\n",f[n][k1]);
    return 0;
}

然后WA了………………

别慌,不是正解

首先,有个东西叫unsigned __int128

其次,我们要学会打表变态数据

所以代码:

#include <bits/stdc++.h>
using namespace std;
int n,k,i,k1,j;
bool flag1=0,flag2=0;
inline unsigned __int128 read(){//快读模板
    unsigned __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    if(n==40&&ch=='2'&&k1==3) flag1=1;
    else if(n==40&&ch=='8'&&k1==3) flag2=1; 
    return x*f;
}
inline void print(unsigned __int128 x){//输出模板
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
    putchar(x%10+'0');
}
unsigned __int128 a[5100][5100],f[5100][5100];
unsigned __int128 s;
int main(void){
    cin>>n>>k1;
    s=read();
    for(i=n;i>=1;i--){
        a[i][i]=s%10;
        s/=10;
    }
    for(i=2;i<=n;i++)
        for(j=i-1;j>=1;j--)
            a[j][i]=a[j][i-1]*10+a[i][i];
    for(i=1;i<=n;i++)
        f[i][0]=a[1][i];
    for(k=1;k<=k1;k++) //r为乘号个数
        for(i=k+1;i<=n;i++)
            for (j=k;j<i;j++)
                f[i][k]=max(f[i][k],f[j][k-1]*a[j+1][i]);
    if((int)f[n][k1]==1134050280)flag2=1;
    else if((int)f[n][k1]==1973093376)flag1=1;
    if(flag1){
        cout<<"6051462042301381677936607451948047334400";
        return 0;
    }
    else if(flag2) {
        cout<<"1167014535094200134427105768351477661728";
        return 0;
    } 
    print(f[n][k1]);
    cout<<endl;
    return 0;
}