易理解代码20250520：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a[110],s[110],f[110][110];

int main()
{
    int n,K;scanf("%d%d",&n,&K);K++;
    s[0]=0;for(int i=1;i<=n;i++) scanf("%lld",&a[i]),s[i]=s[i-1]+a[i];
    
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++) f[i][1]=s[i];
    for(int k=2;k<=K;k++)//枚举段数
    {
        for(int ed=k;ed<=n;ed++)
        {
        	for(int L=1;L<=ed-(k-1);L++)
            { 
            	int st=ed-L+1;
                f[ed][k]=max(f[ed][k],(s[ed]-s[st-1])* f[st-1][k-1]);
            } 
        }
    }
    LL ans=0;for(int k=1;k<=K;k++)ans=max(ans,f[n][k]);
    printf("%lld",ans);
    return 0;
}

新代码20250519：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a[110],s[110],f[110][110];

int main()
{
    int n,K;scanf("%d%d",&n,&K);K++;
    s[0]=0;for(int i=1;i<=n;i++) scanf("%lld",&a[i]),s[i]=s[i-1]+a[i];
    
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++) f[i][1]=s[i];
    for(int k=2;k<=K;k++)//枚举段数
    {
        for(int i=k;i<=n;i++)
        {
            for(int j=i-1;j>=k-1;j--)
            { 
                f[i][k]=max(f[i][k],(s[i]-s[j])*f[j][k-1]);
            } 
        }
    }
    LL ans=0;for(int k=1;k<=K;k++)ans=max(ans,f[n][k]);
    printf("%lld",ans);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a[110],s[110],f[110][110];
//状态设计：f[i][j]代表前i个数了加入j个乘号的最大值
//状态方程：f[i][k]=max( f[j-1][k-1]*(a[j]+~+a[i]) ),k<=j<=i;解释：a[j-1]与a[j]之间为乘号（a[1]~a[j-1]负责k-1个乘号，a[j]~a[i]之间没有乘号）
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    s[0]=0;for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++) f[i][0]=s[i];
    for(int k=1;k<=m;k++)//枚举乘号的数量
    {
        for(int i=k;i<=n;i++)
        {
            for(int j=i;j>=k;j--)
            { 
                f[i][k]=max(f[i][k],(s[i]-s[j-1])*f[j-1][k-1]);
            } 
        }
    }
    LL ans=0;for(int k=0;k<=m;k++)ans=max(ans,f[n][k]);
    printf("%lld",ans);
    return 0;
}