爬塔(分組背包)

連結：https://ac.nowcoder.com/acm/contest/9680/F

來源：牛客網

高川最喜歡的遊戲當屬 Slay the Spire，這是一款爬塔遊戲，你需要從一座塔的底部一直爬到頂部，在爬塔的過程中，塔的每一層都有許多的寶物等你來拿。

高川從塔的左側開始攀爬，從底部爬到頂部，再從右側從頂部逐漸下到底部。塔總共有 n 層，每一層都有很多寶物從左到右排列。在左側攀爬時，他隻能從每層的最左邊按順序取寶物，在右側下降時，他隻能從每層的最右邊按順序取寶物。每個寶物都有一個價值，他最多拿 m 個寶物，他想知道自己從塔上下來時，最多可以拿的寶物價值和是多少。

輸入描述:

第一行輸入兩個正整數 n 和m 。表示塔的層數和最多能選的個數。

接下來 n 行,每行先輸入一個數字 x。表示這一層寶物的個數。接下來輸入 x 個正整數，表示每個寶物的權重 c。

1≤n,x,c≤100

1≤m≤10000

輸入保證可挑選的物品大于等于 m 個.

輸出描述:

輸出一個整數表示高川能拿走的最大價值和.

示例1

輸入

2 3

2 3 2

4 1 4 1 5

輸出

10

#include <stdio.h>
#define max(a, b) (a > b ? a : b)
long long int sum[101][102], num[101][101], f[10001], las[101][102], ans[101][102];
int sz[101], ch[101];
int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("in.txt", "r", stdin);
#endif
    int i, j, n, m, c, k;
    scanf("%d %d", &n, &m);
    for (i = 1; i < n + 1; i++)
    {
        scanf("%d", &sz[i]);
        for (j = 1; j < sz[i] + 1; j++)
        {
            scanf("%lld", &num[i][j]);
            sum[i][j] += sum[i][j - 1] + num[i][j];
        }
    }
    for (i = 1; i < n + 1; i++)
    {
        for (j = sz[i]; j >= 1; j--)
        {
            las[i][j] += las[i][j + 1] + num[i][j];
        }
    }
    for (i = 1; i <= n; i++)
    {
        for (j = 0; j <= sz[i]; j++)
        {
            for (k = 0; k + j <= sz[i]; k++)
            {
                ans[i][j + k] = max(ans[i][j + k], sum[i][j] + las[i][sz[i] - k + 1]);
            }
        }
    }
    for (i = 1; i <= n; i++)
    {
        for (j = m; j > 0; j--)
        {
            for (k = sz[i]; k > 0; k--)
            {
                if (k > j)
                {
                    continue;
                }
                f[j] = max(f[j], f[j - k] + ans[i][k]);
                //printf("%d %d %d %d %d %lld %lld\n",n,i,sz[i],j,k,ans[i][k],f[j]);
            }
        }
    }
    printf("%lld\n", f[m]);
    return 0;
}