题解 P2079 【烛光晚餐】

· · 题解

//本题可以看做一个模板题吧(我认为),因为许多类似题的方法可以按照本题来。如(P2340) 都需要按照题意转化为背包问题。 这里也是如此，先把小明的喜爱度与钱转化为背包来储存小红喜爱度的最大值。 代码：

#include<bits/stdc++.h>
using namespace std;
int f[610][600],n,m,j,k,l;//f数组代表花费n元与小明喜爱程度为m使小红获得喜爱度的最大值
//也可以不压缩(已经压缩了一维)，应该都会01背包的压缩吧。
//因为小明的喜爱度可以为负数，所以根据数据把数组开大一倍。（本应该开1000以上的但是忘记开到那么大就AC了。。。只把第2维开到了600）。假设数组的300位为0,299为-1,301为1，就可以把负数的情况弄到数组里面去了。
struct zzy
{
    int ci,xi,yi;
}sum[1000];
void cot()
{
    int a,b,c,d,e;
    for(a=1;a<=m;a++)
    {
        for(b=0;b<=10;b++)
        cout<<f[a][b]<<" ";cout<<endl;
    }cout<<endl;
}
int main()
{
    //f[n][m]=max f[n-j][m-k]+sum[t].yi,f[n][m]; 
    //状态转移方程
    int a,b,c,d,e;
    cin>>n>>m;
    for(a=1;a<=n;a++)
    cin>>sum[a].ci>>sum[a].xi>>sum[a].yi;
    for(a=1;a<=n;a++)
    {
        for(b=m;b>=sum[a].ci;b--)
        {
        //根据这道菜小明的喜爱度，因为把数组压缩了一维，所以要倒退，所以正数与负数的退发不一样。
            if(sum[a].xi>0)
            {
                for(c=600;c-sum[a].xi>=0;c--)
                {
                //因为在考虑时有许多情况是不可能到达地，所以不能转移，不然会爆错，也就是考虑初始边界情况。
                    if(f[b-sum[a].ci][c-sum[a].xi]==0&&c!=sum[a].xi+300)continue;
                    else
                    f[b][c]=max(f[b][c],f[b-sum[a].ci][c-sum[a].xi]+sum[a].yi);
                }
            }
            else
            {
                for(c=0;c<=600+sum[a].xi;c++)
                {
                    if(f[b-sum[a].ci][c-sum[a].xi]==0&&300-c!=abs(sum[a].xi))continue;
                    else
                    {
                        f[b][c]=max(f[b][c],f[b-sum[a].ci][c-sum[a].xi]+sum[a].yi);
                    }
                }
            }
        }
    }c=0;
    for(a=1;a<=m;a++)
    {
        for(b=300;b<=600;b++)c=max(c,f[a][b]);
    }//取最后小明喜爱度大于0的值。
    if(c>=0)cout<<c;
    else cout<<-1;
}