JZOJ1517. 背包问题

这个题，乍一看感觉挺神的（其实真挺神的），其实是个简单的分组背包（如果恍然大悟就不用接着看了）

取连续的一段是这道题最难以处理的地方，但是观察到物品数量不多<=100（如果恍然大悟就不用接着看了）

不妨把连续取物转化为单个物品，就是说，我们取一段连续物品求和作为一个物品，这样，我们只要满足每组选一个（或不选），

然后这道题就转化为了一个简单的分组背包问题，我们只要通过可行性DP解决就好

#include<iostream>

#include<cstdio>

using namespace std;

int v,t,a[][],tmp[];

bool exi[];

int main()

{

    scanf("%d%d",&v,&t);

    for(int num,i=;i<=t;i++)

    {

        scanf("%d",&num);

        for(int x,j=;j<=num;j++)

        {

            scanf("%d",&x);

            tmp[j]=tmp[j-]+x;

        }

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

            for(int k=j;k<=num;k++)

                a[i][++a[i][]]=tmp[k]-tmp[j-];

    }

    exi[]=;

    for(int k=;k<=t;k++)

        for(int j=v;j;j--)

            for(int tmp,i=;i<=a[k][];i++)

                if((tmp=a[k][i])<=j)

                    exi[j]|=exi[j-tmp];

    int ans=v;

    while(!exi[ans])

        ans--;

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

    return ;

}

秒客网

JZOJ1517. 背包问题

相关文章