P2340 [USACO03FALL] Cow Exhibition G

题目描述

奶牛想证明它们是聪明而风趣的。为此，贝西筹备了一个奶牛博览会，她已经对 $N$ 头奶牛进行了面试，确定了每头奶牛的智商和情商。

贝西有权选择让哪些奶牛参加展览。由于负的智商或情商会造成负面效果，所以贝西不希望出展奶牛的智商之和小于零，或情商之和小于零。满足这两个条件下，她希望出展奶牛的智商与情商之和越大越好，请帮助贝西求出这个最大值。

输入格式

第一行：单个整数 $N$，$1\le N\le 400$。

第二行到第 $N+1$ 行：第 $i+1$ 行有两个整数：$S_i$ 和 $F_i$，表示第 $i$ 头奶牛的智商和情商，− $1000\le S_i;F_i\le 1000$。

输出格式

输出单个整数：表示情商与智商和的最大值。贝西可以不让任何奶牛参加展览，如果这样做是最好的，输出 $0$。

提示

选择第一头，第三头，第四头奶牛，智商和为−5+6+2 = 3，情商和为7−3+1 = 5。再加

入第二号奶牛可使总和提升到10，不过由于情商和变成负的了，所以是不允许的

思路

可以转化成背包问题,这里双商和类似于价值,现在需要考虑的是背包容量应该是什么 注意有个限制,双商之一不能为负,所以双商可以作为容量,按照奶牛-双商进行dp

dp[i][j][k]表示前i头牛,在智商/情商不小于j/k时的最大双商

然后按照多维背包处理....

但是,如果这样处理

int dp[512][1024][1024];

且不说超时了,内存都爆了...x_x

换种方法想,这样dp[i][j][k]的值是j+k,很没必要 于是可以dp[i][j]表示前i头牛在智商大于j - 400000(智商和的范围是-400,000到400,000)时,最大的情商和

最后再遍历所有的dp[N][j],找到最大的dp[N][j] + j就可以了

dp[i][j] = max(dp[n-1][j], dp[n-1][j - cows[i].F])

但是这里仍然需要相当大的内存,所以还是需要优化空间

空间优化-滚动数组

可以发现,每次只用到了dp[n-1],所以可以只开两个数组,来回使用,降低一个维度

还是各种卡和bug，最后决定用搜索，开一个后缀和数组记录后面的最大F和S，如果不可能满足条件则剪枝

提交，居然AC了

题解

// 搜索版
#include <iostream>
#include <cstring>
#include <string>
#define MAXF 400000
using namespace std;

struct cow
{
    int F;
    int S;
};

cow cows[512];
int cnt = 0;

struct
{
    int F;
    int S;
    int sum;
} sums[512], usums[512]; // 后缀和,正后缀和,只记录最大值

int nowmax = 0;

int dfs(int nowcow, int nowf, int nows)
{
    if (nowf + usums[nowcow].F < 0)
    {
        return 0; // 救不了
    }
    else if (nows + usums[nowcow].S < 0)
    {
        return 0;
    }
    else if (nows + nowf + usums[nowcow].sum < nowmax)
    {
        return 0;
    }

    if (nowcow > cnt)
    {
        nowmax = max(nowmax, nowf + nows);
        // if (nowf < 0)
        // {
        //     return 0;
        // }
        // else if (nows < 0)
        // {
        //     return 0;
        // }
        return nowf + nows;
    }
    // 两种选择，要or不要
    return max(dfs(nowcow + 1, nowf, nows), dfs(nowcow + 1, nowf + cows[nowcow].F, nows + cows[nowcow].S));
}

int main()
{

    int N;
    cin >> N;
    int bases = 0;
    int basef = 0;
    // 全正的一定取，全负的一定不取
    for (int i = 1; i <= N; i++)
    {
        int f, s;
        cin >> f >> s;
        if (f >= 0 && s >= 0)
        {
            basef += f;
            bases += s;
            continue;
        }
        else if (f <= 0 && s <= 0)
        {
            continue;
        }
        cnt++;
        cows[cnt].F = f;
        cows[cnt].S = s;
    }

    sums[cnt + 1] = {0, 0, 0};
    usums[cnt + 1] = {0, 0, 0};
    // 计算前缀和
    for (int i = cnt; i >= 1; i--)
    {
        sums[i].F = sums[i + 1].F + cows[i].F;
        sums[i].S = sums[i + 1].S + cows[i].S;
        sums[i].sum = sums[i].F + sums[i].S;

        usums[i].F = usums[i + 1].F;
        usums[i].S = usums[i + 1].S;
        usums[i].sum = usums[i + 1].sum;
        if (cows[i].F > 0)
        {
            usums[i].F = usums[i + 1].F + cows[i].F;
        }
        if (cows[i].S > 0)
        {
            usums[i].S = usums[i + 1].S + cows[i].S;
        }
        if (cows[i].F + cows[i].S > 0)
        {
            usums[i].sum = usums[i + 1].sum + cows[i].S + cows[i].F;
        }
    }

    cout << dfs(1, basef, bases);

    return 0;
}