woj_sherlock.cpp

第四届百度杯预赛解题报告 武汉大学20090315

/**********************************************************************
Author: Sherlock
Created Time:  2009-02-19 16:23:29
File Name: 
Description: 
**********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>

using namespace std;

const int   maxSize     =   100 + 10;

int         n, m;
int         f[maxSize][maxSize], que[maxSize];

void            init()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++)
        scanf("%d", &que[i]);
}

void            solve()
{
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; i ++)
        for (int j = 0; j <= m; j ++)
        {
            f[i][j] = f[i - 1][j];
            int sum = 0;
            for (int k = 1; k <= i; k ++)
            {
                sum += que[i - k + 1];
                if (sum > j)
                    break;
                f[i][j] = max(f[i][j], f[i - k][j - sum] + k * k);
            }
        }
    int ans = 0;
    for (int i = 0; i <= m; i ++)
        if (f[n][i] > ans)
            ans = f[n][i];
    printf("%d\n", ans);
}

int             main()
{
//    freopen("WOJ.out", "w", stdout);
    int test_num;
    scanf("%d", &test_num);
    while (test_num > 0)
    {
        test_num --;
        init();
        solve();
    }
    return 0;
}