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; } View Code
转载于:https://www.cnblogs.com/jason2003/p/6574363.html
相关资源：老人生日祝福词.doc