限量供应
Time limit per test: 4.0 seconds
Time limit all tests: 4.0 seconds
Memory limit: 256 megabytes
华东师大的食堂常常有许多很奇怪的菜，比方说：玉米炒葡萄、玉米炒草莓、玉米炒香蕉……所以很多同学，包括你，去食堂吃东西，是只吃菜，不吃饭的。
但这些菜都是限量供应的：如果你今天点了某一道菜，那么接下来 r 天（不包括今天）你都不能再点这道菜了。当然，同一道菜在同一天内点两份也是不可以的。此外，因为你是从来不吃饭的，所以为了保证能量充足，你每天吃的所有菜的卡路里总和必须大于等于 C。
在本学期的 m 天中，你每天都要在食堂吃。你现在既想吃得多，又不能吃得太多，所以你提出了以下两个要求：
-
在不违背上述条件的前提下，吃的菜的数目（不是种类数）应尽可能多；
-
在不违背 1 的前提下，吃的所有菜的卡路里总和应尽可能小。
Input
第一行是一个整数 T (1≤T，表示测试数据组数。
接下来是 T 组测试数据，每组数据两行。
第一行四个整数 n,m,r,C (1≤n≤12,1≤m≤1000,1≤r≤20,1≤C。其中 n 表示菜的种数，其余变量含义如题中描述。
第二行 n 个整数：c1,c2,…,cn (1≤ci≤105)。
Output
对于每组数据，输出 Case x: y z。x 表示从 1 开始的测试数据编号，y 和 z 分别表示菜的数目和卡路里总和。如果没有满足要求的方案，y 和 z 是 0 0。
Examples
Input
2 7 9 3 3 3 2 2 2 2 3 3 7 5 3 3 3 2 2 2 2 3 3
Output
Case 1: 18 42 Case 2: 11 25
Source
2017 华东师范大学校赛/** 题目：EOJ Problem #3249 链接：http://acm.ecnu.edu.cn/problem/3249/ 题意： 华东师大的食堂常常有许多很奇怪的菜，比方说：玉米炒葡萄、玉米炒草莓、玉米炒香蕉…… 所以很多同学，包括你，去食堂吃东西，是只吃菜，不吃饭的。 但这些菜都是限量供应的：如果你今天点了某一道菜，那么接下来 r 天（不包括今天）你都不能再点这道菜了。 当然，同一道菜在同一天内点两份也是不可以的。此外，因为你是从来不吃饭的，所以为了保证能量充足， 你每天吃的所有菜的卡路里总和必须大于等于 C。 在本学期的 m 天中，你每天都要在食堂吃。你现在既想吃得多，又不能吃得太多， 所以你提出了以下两个要求： 1，在不违背上述条件的前提下，吃的菜的数目（不是种类数）应尽可能多； 2，在不违背 1 的前提下，吃的所有菜的卡路里总和应尽可能小。 , 思路： 预处理s表示满足>=C的菜的集合。 假设总共有n个s满足条件。 那么将n个s。选出来。 排列一行，m个。 保证区间长度r+1范围内的s不能有相同的菜。满足的序列中，取菜的数目最多，然后考虑总卡路里最小。 如果能够找到这样的r+1个s。那么此后都这样循环便是最优。 20*4096 = 81920 dp[i][s]表示前i天选了s集合的菜是否成立。 dp[i][s] = dp[i-1][s']; dp[0][0] = 1; 如果m<r+1; 那么直接就可以遍历dp[m][s]中的s为真时候的s的菜数目num以及花费ans。 如果m>r+1; 遍历dp[r+1][s]中的s为真时候的s的菜数目num以及卡路里花费ans就可以知道m/(r+1)个周期结果为num*(m/(r+1)), ans*(m/(r+1)); 然后还会多余m%(r+1)，知道了r+1的状态s，就可以反向递推获得dp[m%(r+1)][s0]可以得到的s0（因为连续r+1天不能存在相同的， 所以受到前r+1的状态s的影响，通过反向递推解决）.然后计算s0的结果加上那m/(r+1)个周期结果。 注意：r+1天算出的最优的s，不能保证通过这个s反向递推的s0是最优的。我的处理方法是：暴力所有可能的s，然后对每个s反向递推s0. 比较所有的结果中最优的。 */ #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <cstdlib> #include <time.h> using namespace std; typedef long long LL; const int mod=1e9+7; const int maxn=1e6+5; int T, n, m, r, C; LL cost[1<<13]; LL c[13]; int dp[22][1<<13]; int digit[1<<13]; LL num = 0, ans = 0, num1 = 0, ans1 = 0; void init(int n)///ok { int len = 1<<n; for(int i = 0; i < len; i++){ cost[i] = 0; digit[i] = 0; for(int j = 0; j < n; j++){ if(i&(1<<j)){ cost[i]+=c[j]; digit[i]++; } } } } LL num2, ans2; void dfs(int m,int i,int s) { if(i==m){ int cnt = digit[s]; if(cnt>num2){ num2 = cnt; ans2 = cost[s]; }else { if(cnt==num2){ if(cost[s]<ans2){ ans2 = cost[s]; } } } return ; } for(int s0 = s; s0; s0 = (s0-1)&s){ if(cost[s0]<C) continue;///比赛的时候，这道题！！！我少了这行代码。。。唉。dp[i-1][s-s0]如果为真，未必是当前这个状态到来的， ///必须加一个判断条件，判断是否可以由s到s-s0； if(dp[i-1][s-s0]){ dfs(m,i-1,s-s0); } } } int main() { cin>>T; int cas = 1; while(T--) { scanf("%d%d%d%d",&n,&m,&r,&C); for(int i = 0; i < n; i++) scanf("%lld",&c[i]); init(n); memset(dp, 0, sizeof dp); dp[0][0] = 1; int len = 1<<n; int mis = min(r+1,m); for(int i = 1; i <= mis; i++){ for(int s = 1; s < len; s++){ if(cost[s]<C) continue; for(int s0 = s; s0; s0 = (s0-1)&s){ if(cost[s0]<C) continue; dp[i][s] |= dp[i-1][s-s0]; } } } num = 0, ans = 0; if(r+1>=m){ for(int s = 1; s < len; s++){ if(dp[m][s]){ int cnt = digit[s]; if(cnt>num){ num = cnt; ans = cost[s]; }else { if(cnt==num){ if(cost[s]<ans) ans = cost[s]; } } } } }else {///m > r+1; for(int s = 1; s < len; s++){ if(dp[r+1][s]){ ans1 = cost[s]; num1 = digit[s]; num1 = m/(r+1)*num1; ans1 = m/(r+1)*ans1; num2 = ans2 = 0; if(m%(r+1)!=0){ dfs(m%(r+1),r+1,s); } num1 += num2; ans1 += ans2; if(num1>num){ num = num1; ans = ans1; }else { if(num1==num&&ans1<ans){ ans = ans1; } } } } } printf("Case %d: %lld %lld ",cas++,num,ans); } return 0; }