UESTC 876 爱管闲事

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 10007

int a[22],dp[22][22],sum[22];

int SUM(int l,int r)
{
    return sum[r]-sum[l-1];
}

int main()
{
    int t,i,n,m,j,k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        sum[0] = 0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sum[i] = sum[i-1] + a[i];
        }
        for(i=0;i<=21;i++)
        {
            for(j=0;j<=i;j++)
                dp[i][j] = 1;
            for(j=i+1;j<=21;j++)
                dp[i][j] = 0;
        }
        for(i=1;i<=n;i++)
        {
            int s = 1;
            for(j=1;j<=i;j++)
                s *= a[j];
            dp[i][i] = s;
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=i;j++)
            {
                int maxi = -1;
                for(k=j-1;k<i;k++)
                {
                    maxi = max(maxi,dp[k][j-1]*SUM(k+1,i));
                }
                dp[i][j] = max(maxi,dp[i][j]);
            }
        }
        printf("%d\n",dp[n][m]);
    }
    return 0;
}