UVA - 12563 Jin Ge Jin Qu hao （01背包变形）

　　此题应该注意两个点，首先背包容量应该缩减为t-1，因为最长的歌不超过三分钟，而劲歌金曲有678s，所以肯定要留出这个时间来。其次注意优先级，保证唱的歌曲数目最多，在此前提下尽可能的延长时间。

　　处理方法：开创结构体，在歌曲数目相等的时候，选取最长时间。

　　注意：注意t的大小，t完全没有必要计算那么大的数据。代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define N 10010

int w[];

struct DP

{

    int song,tim;

}dp[N];

int main()

{

//    freopen("1.in.cpp","r",stdin);

    int T,n,t,ca=,sum;

    cin>>T;

    while(T--)

    {

        cin>>n>>t;

        sum = ;

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

                cin>>w[i];

                sum += w[i];

        }

        if(t > sum){

            if(t < sum + ) t = sum + ;

            printf("Case %d: %d %d\n",++ca,n+,t);

            continue;

        }

        t--;

        for(int i = ;i < N;i++) dp[i].song = dp[i].tim = ;

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

        {

            for(int j = t; j >= w[i]; j--)

            {

                if(dp[j-w[i]].song+ > dp[j].song)

                {

                    dp[j].song = dp[j-w[i]].song + ;

                    dp[j].tim = dp[j-w[i]].tim + w[i];

                }

                if(dp[j-w[i]].song+ == dp[j].song)

                {

                    dp[j].tim = max(dp[j].tim,dp[j-w[i]].tim + w[i]);

                }

            }

        }

        printf("Case %d: %d %d\n",++ca,dp[t].song+,dp[t].tim+);

    }

    return ;

}

巴特西

UVA - 12563 Jin Ge Jin Qu hao （01背包变形）

最新文章

热门文章