题意
题目背景
小明准备请小红去一家咖啡厅，共进烛光晚餐。小红高兴地和他一起去了咖啡厅。
题目描述
小红说：“小明，你点菜吧。”小明看到菜单上有(N)道菜，每道菜的价格是(C_i)。小明对每道菜的喜爱程度是(X_i)，小红对每道菜的喜爱程度是(Y_i)。（喜爱程度可能为负数）（小明：以我对她的了解，我给你的数据不会错的）
小明带了(V)元钱，他点的菜的总价格不能超过(V)（小明：当然得我请客啦，显得我大方。）
小明希望让小红吃得开心，所以当然要让她的总喜爱程度尽量大。当然，小明也要考虑自己的感受，点的所有菜的总喜爱程度需要大于等于(0)。（小明：要是我吃得不好，她看见我会难过的）
请你帮小明写一个程序，计算出他的总喜爱程度大于等于(0)的前提下，小红的喜爱程度的最大值。（小明：你的程序一定要靠谱啊，我得给她一个好印象）
输入输出格式
输入格式：
第(1)行，两个正整数(N,V)。
之后(N)行，每行(3)个空格隔开的正整数(C_i)，整数(X_i,Y_i)。
输出格式：
一行，一个正整数，表示他的总喜爱程度大于等于(0)的前提下，小红的喜爱程度的最大值。如果这个最大值小于(0)，输出(-1)。
输入输出样例
输入样例#1：
4 10
5 -1 3
2 2 2
11 -5 100
3 -3 10
输出样例#1：
5
说明
对于(10\%)数据，(N<=10,V<=50)。
对于(30\%)数据，(X_i,Y_igeq 0)。
对于全部数据，(Nleq 100,Vleq 500,|X_i|leq 5,|Y_i|leq 1000)。
思路
负数域下的背包问题。定义(dp[i][j])为花费为(i)，小明喜爱程度为(j)时小红的最大喜爱程度。直接转移就好啦。
[dp[i][j]=max{ dp[i][j],dp[i-c][j-x]+y}
]
因为(j-x)可能是负数，所以数组要开到负数域上，这样宏定义一下就好啦：
#define f(a,b) dp[a][b+500]
然后转移时直接用(f)，就是简单的背包问题了。
AC代码
#include<bits/stdc++.h>
using namespace std;
int n,v,dp[505][1005],ans=-1;
#define f(a,b) dp[a][b+500]
int read()
{
bool f=true;int re=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=false;ch=getchar();}
while(isdigit(ch)) re=(re<<3)+(re<<1)+ch-'0',ch=getchar();
return f?re:-re;
}
int main()
{
n=read(),v=read();
memset(dp,0xcf,sizeof dp);
f(0,0)=0;
for(int i=1;i<=n;i++)
{
int x=read(),y=read(),z=read();
for(int j=v;j>=x;j--)
for(int k=500;k>=-500;k--)
if(k-y>=-500&&k-y<=500)
f(j,k)=max(f(j,k),f(j-x,k-y)+z);
}
for(int i=0;i<=v;i++)
for(int j=0;j<=500;j++)
ans=max(ans,f(i,j));
printf("%d",ans);
return 0;
}