题意：
假定你在唱KTV，还剩下t秒时间。你决定接下来唱你最喜爱的n首歌（不包含劲歌金曲）中的一些歌曲。在时间结束之前再唱一个劲歌金曲。使得唱的歌的总曲目尽量多以及时间总长度。
输入保证所有n+1曲子的时间长度严格大于t。
题解：
每一首歌的时间长度不超过3分钟，最多50首歌，所以时间t最大也是180*n+678。这样就可以转化为01背包问题。
但是这个问题有约束条件：唱的歌曲尽量多，和时间总长要长。因为第一个的条件优先。所以：
当num[j - w[i]] + 1 > num[j] 时，更新歌曲数和用时。
当num[j - w[i]] + 1 == num[j] 时，只更新时间。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <string> 7 #include <vector> 8 #include <map> 9 #include <set> 10 #include <queue> 11 #include <sstream> 12 #include <algorithm> 13 using namespace std; 14 #define pb push_back 15 #define mp make_pair 16 #define ms(a, b) memset((a), (b), sizeof(a)) 17 //#define LOCAL 18 #define eps 0.0000001 19 typedef long long LL; 20 const int inf = 0x3f3f3f3f; 21 const LL INF = 0x7fffffff; 22 const int maxn = 100+10; 23 const int mod = 1000000007; 24 int w[60]; 25 int dp[10000]; 26 int num[10000]; 27 int kase = 1; 28 void init() 29 { 30 ms(w, 0); 31 ms(dp, 0); 32 ms(num, 0); 33 } 34 void solve() 35 { 36 int n, t, sum = 0; 37 scanf("%d%d", &n, &t); 38 for(int i = 1;i<=n;i++) scanf("%d", &w[i]), sum+=w[i]; 39 for(int i = 1;i<=n;i++){ 40 for(int j = t-1 ; j >= w[i];j--){ 41 if(num[j-w[i]] + 1 > num[j] ){ 42 num[j] = num[j-w[i]] + 1; 43 dp[j] = dp[j-w[i]] + w[i]; 44 } 45 else if(num[j-w[i]] + 1 == num[j] && dp[j-w[i]] + w[i] > dp[j] ){ 46 dp[j] = dp[j-w[i]] + w[i]; 47 } 48 } 49 } 50 printf("Case %d: %d %d ", kase++, num[t-1]+1, dp[t-1]+11*60+18); 51 } 52 int main() { 53 #ifdef LOCAL 54 freopen("input.txt", "r", stdin); 55 // freopen("output.txt", "w", stdout); 56 #endif // LOCAL 57 int T; 58 scanf("%d", &T); 59 while(T--){ 60 init(); 61 solve(); 62 } 63 return 0; 64 }
你努力的时候，比你厉害的人也在努力。