UVa 12563_Jin Ge Jin Qu hao

【题意】在KTV唱歌，假设每首歌最长180s，时间结束时如果还有歌正在唱，则将此歌唱完。为使唱歌时间最长，规定最后唱长达678s的《劲歌金曲》【介是个嘛？】

假设你正在唱KTV，在剩余的t秒时间里，在给定时长的n首歌里（不包括劲歌金曲），要尽可能的多唱。即在唱的总曲目尽量多的前提下，尽量晚的离开KTV。求唱的总曲目及唱的时间总长度。

【分析】01背包先求最大的曲目数，再在此前提下求从最后遍历数组获取此前提下的最长时间，最后输出加上678

【代码】

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <set>

#include <map>

#include <algorithm>

#include <stack>

#include <queue>

#include <cmath>

#include <ctime>

using namespace std;

int v[100000];

int t[60];

int n,total;

const int mod=int(1e9)+7,INF=-1000000000,maxn=1e5+40;

void ZeroOnePack(int Case)

{

    fill(v,v+100000,INF);

    v[0]=0;

    int temp=0;

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

    {

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

        {

            v[j]=max(v[j],v[j-t[i]]+1);

            if(v[j]>temp) temp=v[j];

        }

    }

    for(int i=total-1;i>=0;i--)

    {

        if(v[i]==temp)

        {

            cout<<"Case "<<Case+1<<": "<<temp+1<<" "<<i+678<<endl;

           return;

        }

    }

}

int main (void)

{

    int Case;

    int Max=0;

    cin>>Case;

    for(int i=0;i<Case;i++)

    {

        cin>>n>>total;

        memset(t,0,sizeof(t));

        for(int j=0;j<n;j++) cin>>t[j];

        ZeroOnePack(i);

    }

}

巴特西

UVa 12563_Jin Ge Jin Qu hao

最新文章

热门文章