生日劲歌会

试题描述

Davs到KTV唱歌庆祝生日，他妈妈给他买单的时间是n个单位时间，但KTV不会时间到就立刻鲁莽地把正在唱的歌切掉，而是等它放完，这样消费者就会多一些唱歌时间。例如，你在还有15秒时再唱一首3分钟的歌，你就会多唱165秒。现在KTV提供了Davs喜爱的n首歌，请你为Davs安排点歌的顺序，使得Davs尽可能唱更多曲目，而且离开歌厅的时间越晚越好。曲目不能重复。（中间不能空余时间）

输入

第一行包含一个正整数n，接下来的若干行，每行包含一个正整数，描述一首歌曲的时间。

输出

一行，包含两个数，依次为点播歌曲的总数目和播放歌曲的总时间

输入示例

350 120 80 79 300 75 66 84 45

输出示例

6 649

其他说明

n<=10000.数字个数<=5000个

#include <iostream>
using namespace std;
int a[10010],b[10010],c[10010],n,v;
int main()
{
    cin>>v; 
    v--;   
    int k=1;
    while(cin>>a[k])
        k++;
    sort(a,a+k);
    int large=a[k-1];
    for(int i=1;i<=k;i++)
        for(int j=v;j>=a[i];j--)
            if(c[j]<c[j-a[i]]+1 || (c[j]==c[j-a[i]]+1 && b[j]<b[j-a[i]]+a[i]))
            {
                b[j]=b[j-a[i]]+a[i];
                c[j]=c[j-a[i]]+1;
            }
    int t=v-b[v];
    cout<<c[v]<<" "<<v+large-t;
}