UVA 12563 Jin Ge Jin Qu hao(01背包变形:两个条件最优化)

妖狐艹你老母 2021-12-19 02:51 182阅读 0赞

## 题意:KTV里面有n首歌曲你可以选择,每首歌曲的时长都给出了. 对于每首歌曲,你最多只能唱1遍. 现在给你一个时间限制t (t<=10^9) , 问你在最多t-1秒的时间内可以唱多少首歌曲num , 且最长唱歌时间是多少time (time必须<=t-1) ? 最终输出num+1 和 time+678 即可，注意: 你需要优先让歌曲数目最大的情况下,再去选择总时长最长的. ##

## 分析:典型01背包问题，dp\[i\]\[j\]==x 表示当决策完全前i个物品（歌曲）后(选或不选), 所选的总歌曲时长<=j时, 所得到的**最优状态**为x. (**这里的x就不是平时我们所说的最长时间或最多歌曲数目了**)。总时长最长的逆推dp\[n\]\[t-1\]找出来就好了。代码通过异或运算（滚动数组）节省内存。 ##

## 代码： ##

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn = 50 + 5;
    const int INF = 1000000000;
    int n, t, len[maxn], d[2][maxn*180+678];
    
    int main()
    {
        int T;
        scanf("%d", &T);
        for(int kase = 1; kase <= T; kase++)
        {
            scanf("%d%d", &n, &t);
            int sum=0;
            for(int i = 1; i <= n; i++) scanf("%d", &len[i]),sum+=len[i];
            t=min(t,sum+678);
            for(int i = 0; i < t; i++) d[0][i] = -1;
            d[0][0] = 0;
    
            int p = 1, ans = 0;
            ///01背包 异或交替 相当于滚动数组节省内存
            for(int i = 1; i <= n; i++)
            {
                for(int j = 0; j < t; j++)
                {
                    d[p][j] = d[p^1][j];
                    if(j >= len[i] && d[p^1][j - len[i]] >= 0)
                        d[p][j] = max(d[p][j], d[p^1][j - len[i]] + 1);
                    ans = max(ans, d[p][j]);
                }
                p ^= 1;
            }
            ///逆推求唱歌总时间最长
            for(int i = t-1; i >= 0; i--)
                if(d[p^1][i] == ans)
                {
                    printf("Case %d: %d %d\n", kase, ans + 1, i + 678);
                    break;
                }
        }
        return 0;
    }