UVa-12563 劲歌金曲

题目

https://vjudge.net/problem/Uva-12563

给出n首歌和KTV的剩余时间T,因为KTV不会在时间到的时候立刻把歌切掉,而是会等它放完.而《劲歌金曲》长达678秒,因此你可以在从你喜欢的歌中选择一些,在时间结束前再唱一首《劲歌金曲》.

给出一种策略,使得唱的歌曲尽可能的多,在此前提下,使得唱的时间尽可能的长.

分析

和一般的01背包相比,本题有歌曲数目和歌曲长度两个优化目标,优先使歌曲数目最多,如果歌曲数目相同,则使歌曲长度最长.

因此可以写一个结构体描述上述属性

struct Node{

    int num;//歌曲数量

    int time;//歌曲总时间

    bool operator < (Node n){

        return num < n.num || (num==n.num && time < n.time);

    }

};

其余与一般的01背包没有大的区别

AC代码

#include "bits/stdc++.h"

using namespace std;

int t[55];//记录每首歌的时间

const int maxn = 180*50+5;

struct Node{

    int num;//歌曲数量

    int time;//歌曲总时间

    bool operator < (Node n){

        return num < n.num || (num==n.num && time < n.time);

    }

}dp[maxn];

int main(int argc, char const *argv[])

{

    int C, n, T, i, j;

    cin >> C;

    int Case = 0;

    while(Case++ < C){

        cin >> n >> T;

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

            cin >> t[i];

        }

        T--;

        memset(dp, 0, sizeof(dp));

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

            for(j=T;j>=t[i];j--){

                Node temp;

                temp.num = dp[j - t[i]].num + 1;

                temp.time = dp[j - t[i]].time + t[i];

                if(dp[j] < temp) dp[j] = temp;

            }

        }

        cout << "Case " << Case << ": " << dp[T].num+1 << ' ' << dp[T].time+678 << endl;

    }

    return 0;

}

巴特西

UVa-12563 劲歌金曲

题目

分析

AC代码

最新文章

热门文章