原题链接

题解

1.考虑到每个牛只有选或不选两种选择，这样暴力搜索的思路便产生了
2.还是上面的思路，怎么优化呢？
想想背包数组，其下标是什么？是体积
其值是是什么？是价值
是在体积相同的情况下选择价值最高的，本题也是，最优解一定是相同智商里情商最高的
3.价值和体积都是负数，怎么解决？

code

#include<bits/stdc++.h>
using namespace std;
int dp[800008]={0},vis[800008]={0};
struct
{
    int i,e;
}cow[405];
int main()
{
    memset(dp,-0x3f,sizeof dp);
    dp[400000]=0;//移动坐标轴，把400000看成零点
    vis[400000]=1;
    int n;
    cin>>n;
    int tot=0;
    for(int i=1;i<=n;i++) cin>>cow[i].i>>cow[i].e;


    for(int i=1;i<=n;i++)
    {
        if(cow[i].i>=0)
        {
            for(int k=800000;k>=cow[i].i;k--)
            {
                if(vis[k-cow[i].i])
                {
                    dp[k]=max(dp[k],dp[k-cow[i].i]+cow[i].e);
                    //printf("%d:%d\n",k,dp[k]);
                    vis[k]=1;
                }
            }
        }
        else
        {
            for(int k=0;k<=800000+cow[i].i;k++)//如果智商是负数，滚动数组要倒着来
            {
                if(vis[k-cow[i].i])
                {
                    dp[k]=max(dp[k],dp[k-cow[i].i]+cow[i].e);
                    //printf("%d:%d\n",k,dp[k]);
                    vis[k]=1;
                }
            }
        }
    }

    int ans=0;
    for(int i=400000;i<=800000;i++)
    {
        if(vis[i]&&dp[i]>=0)ans=max(ans,dp[i]+i-400000);
    }
    cout<<ans;
    return 0;
}