本文共 679 字,大约阅读时间需要 2 分钟。
因为题目给出的时间很大,但是实际上不需要这么多的时间,因为一共50首歌,一个最多3分钟,所以最多180*50时间,所以如果题目(给出的时间-1)大于总歌曲时间的话,直接输出总时间+678。剩下的情况则进行dp。判断的标准是在歌曲数目和歌曲时间进行判断的。
#include#include #include #include using namespace std;const int maxn=55;int t;int n,m;int a[maxn];struct node { int num; int time;};node dp[10000];int compare (node a,node b){ if(a.num =tot) { printf("%d %d\n",n+1,tot+678); continue; } memset (dp,0,sizeof(dp)); for (int i=1;i<=n;i++) { for (int j=m-1;j>=a[i];j--) { node tep; tep.num=dp[j-a[i]].num+1; tep.time=dp[j-a[i]].time+a[i]; if(compare(dp[j],tep)) dp[j]=tep; } } printf("%d %d\n",dp[m-1].num+1,dp[m-1].time+678); } return 0;}
转载地址:http://fkoen.baihongyu.com/