HDU3535AreYouBusy（分组背包）

http://acm.hdu.edu.cn/showproblem.php?pid=3535

分组背包，每一组加了以下三个限制

            0 stands for the sets that should choose at least 1 job to do,

            1 for the sets that should choose at most 1 ,

            2 for the one you can choose freely

HDU3535AreYouBusy（分组背包）

#include <map>

#include <set>

#include <stack>

#include <queue>

#include <cmath>

#include <ctime>

#include <vector>

#include <cstdio>

#include <cctype>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

#define INF 0x3f3f3f3f

#define MAX(a,b) (a > b ? a : b)

#define MIN(a,b) (a < b ? a : b)

#define mem0(a) memset(a,0,sizeof(a))

#define mem1(a) memset(a,-1,sizeof(a))

#define lson k<<1, L, mid

#define rson k<<1|1, mid+1, R

typedef long long LL;

const double eps = 1e-;

const int MAXN = ;

const int MAXM = ;

int n, T, m, s;

int DP[][];

int cost[], val[];

int main()

{

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

    {

        for(int i=;i<=T;i++) DP[][i]=;

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

        {

            scanf("%d%d", &m, &s);

            for(int j=;j<m;j++) scanf("%d%d", &cost[j], &val[j]);

            if(s==) {

                for(int k=;k<=T;k++) DP[i][k] = -INF;// 这样确保最少放一个物品

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

                for(int k=T;k>=cost[j];k--) {

                    //** 如果是第一次选，则一定能加入数组中

                    //** 如果不是第一次选，则当做普通01背包处理

                    DP[i][k] = max(DP[i][k], max(DP[i][k-cost[j]]+val[j], DP[i-][k-cost[j]]+val[j]));

                }

            }

            else if(s==) {

                // 为了保证全局最优解，初始化为上一次结果

                for(int k=;k<=T;k++) DP[i][k] = DP[i-][k];

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

                for(int k=T;k>=cost[j];k--) {

                    DP[i][k] = max(DP[i][k], DP[i-][k-cost[j]]+val[j]);

                }

            }

            else if(s==) {

                for(int j=;j<=T;j++)DP[i][j] = DP[i-][j];

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

                for(int k=T;k>=cost[j];k--) {

                    DP[i][k] =max(DP[i][k], max(DP[i-][k-cost[j]]+val[j], DP[i][k-cost[j]]+val[j]));

                }

            }

        }

        printf("%d\n", max(DP[n][T], -));

    }

    return ;

}

秒客网

HDU3535AreYouBusy（分组背包）

相关文章