限量供应
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≤100)，表示测试数据组数。
接下来是 T 组测试数据，每组数据两行。
第一行四个整数 n,m,r,C (1≤n≤12,1≤m≤1000,1≤r≤20,1≤C≤105)。其中 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+;
const int maxn=1e6+;
int T, n, m, r, C;
LL cost[<<];
LL c[];
int dp[][<<];
int digit[<<];
LL num = , ans = , num1 = , ans1 = ;
void init(int n)///ok
{
int len = <<n;
for(int i = ; i < len; i++){
cost[i] = ;
digit[i] = ;
for(int j = ; j < n; j++){
if(i&(<<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-)&s){
if(cost[s0]<C) continue;///比赛的时候，这道题！！！我少了这行代码。。。唉。dp[i-1][s-s0]如果为真，未必是当前这个状态到来的，
///必须加一个判断条件，判断是否可以由s到s-s0；
if(dp[i-][s-s0]){
dfs(m,i-,s-s0);
}
} }
int main()
{
cin>>T;
int cas = ;
while(T--)
{
scanf("%d%d%d%d",&n,&m,&r,&C);
for(int i = ; i < n; i++) scanf("%lld",&c[i]);
init(n);
memset(dp, , sizeof dp);
dp[][] = ;
int len = <<n;
int mis = min(r+,m);
for(int i = ; i <= mis; i++){
for(int s = ; s < len; s++){
if(cost[s]<C) continue;
for(int s0 = s; s0; s0 = (s0-)&s){
if(cost[s0]<C) continue;
dp[i][s] |= dp[i-][s-s0];
}
}
} num = , ans = ;
if(r+>=m){
for(int s = ; 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 = ; s < len; s++){
if(dp[r+][s]){
ans1 = cost[s];
num1 = digit[s];
num1 = m/(r+)*num1;
ans1 = m/(r+)*ans1;
num2 = ans2 = ;
if(m%(r+)!=){
dfs(m%(r+),r+,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\n",cas++,num,ans);
}
return ;
}