A - 愛管閒事

春希非常愛管閒事，他每天都會抽空幫助一些同學，由於春希非常死板，出於公平性，春希不會先幫助後來找他的同學。

現在有n個同學需要他的幫助，雖然他很想一天之類幫助所有人，但畢竟精力有限，於是他決定分m天來幫助他們。

根據事情的重要性，春希幫助不同同學會有不同的快樂值，而春希獲得的總的快樂值為每天獲得的快樂值的乘積。

現在給出n和m，以及幫助完各同學時獲得的快樂值，求春希能獲得的最大快樂值。

Input

第一行為一個整數T，代表數據組數。

每組數據，第一行兩個整數n,m。表示需要幫助的同學的數量，和天數。(1≤m≤min(n,10),1≤n≤20)

第二行為n個整數，表示幫助這個同學的獲得的快樂值，每個快樂值不大於5。

Output

每組數據輸出一行，一個整數，表示最大的快樂值。

Sample input and output

Sample Input Sample Output

1
5 3
3 2 1 4 5

125

解題思路： dp[j][i]表示前j個數分為i部分的和的乘積的最大值。測試用例中(3+2)*(1+4)*5=125 三重循環。 dp[j][i]=max(dp[j][i],dp[k][i-1]*(sum[j]-sum[k])); 關鍵代碼：

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

代碼：

#include 
#include 
#include 
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一開始寫的一維的，可是一直WA，不知道為什麼，求解。

錯誤的一維代碼：

#include 
#include 
#include 
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