春希很爱管闲事，他每天都会抽出时间帮助一些同学，因为春希很死板，出于公平性，春希不会先帮助后来找他的同学。

如今有n个同学须要他的帮助，尽管他非常想一天之类帮助全部人，但毕竟精力有限，于是他决定分m天来帮助他们。

依据事情的重要性，春希帮助不同同学会有不同的快乐值。而春希获得的总的快乐值为每天获得的快乐值的乘积。

如今给出n和m，以及帮助完各同学时获得的快乐值，求春希能获得的最大快乐值。

Input

第一行为一个整数T。代表数据组数。

每组数据。第一行两个整数n,m。

表示须要帮助的同学的数量，和天数。(1≤m≤min(n,10),1≤n≤20)

第二行为n个整数，表示帮助这个同学的获得的快乐值，每一个快乐值不大于5。

Output

每组数据输出一行。一个整数。表示最大的快乐值。

Sample input and output

1

5 3

3 2 1 4 5

125

解题思路：

for(int i=1;i<=m;i++)

            for(int j=n;j>=i;j--)

                for(int k=i-1;k<j;k++)

        {

            dp[j][i]=max(dp[j][i],dp[k][i-1]*(sum[j]-sum[k]));

        }

代码：

#include <iostream>

#include <algorithm>

#include <string.h>

using namespace std;

const int maxn=25;

int dp[maxn][maxn];

int num[maxn],sum[maxn];

int t,n,m;

int main()

{

    cin>>t;

    while(t--)

    {

        cin>>n>>m;

        for(int i=0;i<=n;i++)

            for(int j=0;j<=m;j++)

            dp[i][j]=1;

        sum[0]=0;

        for(int i=1;i<=n;i++)

        {

            cin>>num[i];

            sum[i]=sum[i-1]+num[i];

        }

        for(int i=1;i<=m;i++)

            for(int j=n;j>=i;j--)

                for(int k=i-1;k<j;k++)

        {

            dp[j][i]=max(dp[j][i],dp[k][i-1]*(sum[j]-sum[k]));

        }

        cout<<dp[n][m]<<endl;

    }

    return 0;

}

一開始写的一维的。但是一直WA，不知道为什么，求解。

#include <iostream>

#include <string.h>

#include <algorithm>

using namespace std;

int sum[25];

int num[25];

int dp[25];

int t;

int n,m;

int main()

{

    cin>>t;

    while(t--)

    {

        sum[0]=0;

        dp[0]=1;

        cin>>n>>m;

        for(int i=1;i<=n;i++)

        {

            cin>>num[i];

            sum[i]=sum[i-1]+num[i];

            dp[i]=1;

        }

        for(int i=1;i<=m;i++)

        {

            for(int j=n;j>=i;j--)

            {

                for(int k=i-1;k<j;k++)

                {

                    dp[j]=max(dp[j],dp[k]*(sum[j]-sum[k]));

                }

            }

        }

        cout<<dp[n]<<endl;

    }

    return 0;

}