WOJ 1538 Stones II 转化背包问题

昨天是我负责这个题目的，最后没搞出来，真的给队伍拖后腿了。

当时都推出来了我假设最后结果是取了m个物品，则我把这个m个物品按取的先后编号为 k1 k2 k3 k4...km

则最终结果就是 (k1.a+k2.a+...km.a)-((m-1)*k1.b+(m-2)*k2.b+....+1*k(m-1).b+0*km.b);

由此可见最终的结果必定是从n个石头中选出m个石头，而且这m个石头要按b值的升序来取，因为按上述式子，这m个石头的a值顺序不影响结果，但b值越小的放前面就使得结果越优，这里也算用了一下贪心思想吧，不过是显而易见的。

然后当时聪哥就照着这个敲了一个贪心的，WA了。。。之后就肯定了绝对不仅仅用贪心来解

然后一直到比赛结束，我都没想到合适的方法来解。。。

其实已经给定了取的顺序，在n个物品中取m件使得价值最大。。。这不就是典型的背包问题嘛。。。哎，我真的是觉得自己当时脑袋短路的可以

于是我们定义一个d[i][j],表示当前第i件物品放到j位置的最大值（当然该件物品也可以不取，但这个状态必须保留下来）。

于是我们把b值按降序排序。从后往前来取石头比较好算一点。

d[i][j]=max(d[i-1][j],d[i-1][j-1]+ai-(j-1)*bi)

d[i-1][j]就代表当前这个物品我不取，后面那个就代表取，但是我就有点纠结这个（j-1）*bi这里，因为我背包过程中，d[i][j]虽然是规定了i件物品在在第j次取，但是之前也存在不取的情况，那此时这个石头还是第j次取吗？后来我发现自己想多了，首先按我的定义这个式子是肯定没错的，其次，如果结果最终是存在一个取石头的序列，那么必定就能通过这个式子来得到结果。。否则就是0了。就是把i件物品在各个位置的值都求一下，最后总结起来就存在那样的放置方法即可。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 1010

using namespace std;

int d[N][N];

struct node

{

    int a,b;

    bool operator <(const node &rhs) const

    {

        if (b==rhs.b)

            return a>rhs.a;

        return b>rhs.b;

    }

} s[N];

int main()

{

    int n;

    while (scanf("%d",&n) && n)

    {

        for (int i=;i<=n;i++)

            scanf("%d%d",&s[i].a,&s[i].b);

        sort(s+,s++n);

        memset(d,,sizeof d);

        for (int i=;i<=n;i++)

        {

            for (int j=;j<=i;j++)

            {

                d[i][j]=max(d[i-][j],d[i-][j-]+s[i].a-(j-)*s[i].b);

            }

        }

        int ans=;

        for (int i=;i<=n;i++)

            ans=max(ans,d[n][i]);

        printf("%d\n",ans);

    }

    return ;

}

巴特西

WOJ 1538 Stones II 转化背包问题

最新文章

热门文章