寒假集训——AreYouBusy

Z时代
2024-01-10
分类：综合

coding

题目链接

题意：n~100组工作，有的组必须选一个去做，有的组最多选一个去做，有的组随意，t~100个时间，每个工作有一个花费时间和一个收益，求收益最大是多少。

题解：不同组的不同方式处理，必须选一个，那么就强制先选一个，但是会有没办法强制选的（时间太少）情况，所以先所有都设为INF，然后对每一个物品，可能是第一次选，可能是接着上次的选；最多选一个，每次都用上次的更新；而随便的就是01背包。不要忘了先拷贝上一个i - 1的情况到i

重点：最少选一个，最多选一个的分组背包。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <ctype.h>
#include <limits.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#include <bitset>
#define CLR(a) memset(a, 0, sizeof(a))
#define REP(i, a, b) for(int i = a;i < b;i++)
#define REP_D(i, a, b) for(int i = a;i <= b;i++)
typedef long long ll;
using namespace std;
const int maxn = 110;
const int MIN = -10000000;
int tot, n, kinds[maxn], num[maxn], t[maxn][maxn], h[maxn][maxn];
int dp[maxn][maxn];
void getDp()
{
    for(int i = 1; i <= tot; i++)
    {
        dp[0][i] = MIN;
    }
    dp[0][0] = 0;
    for(int i = 1; i <= n; i++)
    {
        if(kinds[i] == 0)
        {
            for(int k = 0; k <= tot; k++)//必须选，此时是不对的情况
            {
                dp[i][k] = MIN;
            }
            for(int j = 1;j <= num[i];j++)
            {
                for(int k = tot;k >= 0;k--)
                {
                    if(k >= t[i][j] && dp[i][k - t[i][j]] != MIN)//不是第一次选，接着选
                    {
                        dp[i][k] = max(dp[i][k], dp[i][k - t[i][j]] + h[i][j]);
                    }
                    if(k >= t[i][j] && dp[i - 1][k - t[i][j]] != MIN)//是第一次选
                    {
                        dp[i][k] = max(dp[i][k], dp[i - 1][k - t[i][j]] + h[i][j]);
                    }
                }
            }
        }
        else if(kinds[i] == 1)
        {
            for(int k = 0;k <= tot;k++)//先拷贝，可能一个都不选。
            {
                dp[i][k] = dp[i - 1][k];
            }
            for(int j = 1;j <= num[i];j++)
            {
                for(int k = tot;k >= 0;k--)//用上一次的来更新
                {
                    if(k - t[i][j] >= 0 && dp[i - 1][k - t[i][j]] != MIN)
                        dp[i][k] = max(dp[i][k], dp[i - 1][k - t[i][j]] + h[i][j]);
                }
            }
        }
        else if(kinds[i] == 2)
        {
            for(int k = 0;k <= tot;k++)
            {
                dp[i][k] = dp[i - 1][k];//拷贝
            }
            for(int j = 1;j <= num[i];j++)
            {
                for(int k = tot;k >= 0;k--)
                {
                    if(k - t[i][j] >= 0 && dp[i][k - t[i][j]] != MIN)//普通01背包
                        dp[i][k] = max(dp[i][k], dp[i][k - t[i][j]] + h[i][j]);
                }
            }
        }
    }
}
void solve()
{
    getDp();
    int ans = -1;
    for(int i = 0;i <= tot;i++)
    {
        ans = max(ans, dp[n][i]);
    }
    if(ans < 0)
    {
        printf("-1\n");
    }
    else
    {
        printf("%d\n", ans);
    }
}
int main()
{
   // freopen("12Lin.txt", "r", stdin);
    //freopen("1out.txt", "w", stdout);
    while(scanf("%d%d", &n, &tot) != EOF)
    {
        REP_D(i, 1, n)
        {
            scanf("%d%d", &num[i], &kinds[i]);
            REP_D(j, 1, num[i])
            {
                scanf("%d%d", &t[i][j], &h[i][j]);
            }
        }
        solve();
    }
    return 0;}