14264. 珅泽教育CSP-J第一轮模拟考第二十套 第 44 题

珅泽教育CSP-J第一轮模拟考第二十套 第 44 题

完善程序第2题:两组等和的最大值

给定 n=256n=256 个正整数 a0,…,a255a_0,\ldots,a_{255}。每个元素的数据范围是 0<ai≤2100<a_i\leq 2^{10}。可以删去任意多的数字,要求剩下的数字可以分成两组,且两组数字之和完全相等,返回这个和的最大值。

const int n = 256;
int a[n];
const int maxa = 1 << 10;
const int maxd = n * maxa;
int mem[2][maxd];

int fetch(int i, int d)
{
    if (d < 0)
    {
        return _____(1)_____;
    }
    else if (d >= maxd)
    {
        return _____(2)_____;
    }
    else if (i == n)
    {
        if (d == 0)
        {
            return 0;
        }
        else
        {
            return -maxd;
        }
    }
    else
    {
        return _____(3)_____;
    }
}

void store(int i, int d)
{
    int x = _____(4)_____;
    int y = _____(5)_____;
    int z = fetch(i + 1, d);
    mem[i % 2][d] = std::max(x, std::max(y, z));
}

int solve()
{
    for (int i = n; i > 0; --i)
    {
        for (int d = 0; d < maxd; d++)
        {
            _____(6)_____;
        }
    }
    return _____(7)_____;
}

(5)处应填( )。

{{ select(1) }}

  • store(i - 1, d + a[i])
  • fetch(i + 1, d - a[i])
  • fetch(i + 1, d) + a[i]
  • fetch(i + 1, d - a[i]) + a[i]