题目链接：这里
题意：给了n段路，每段路长度不同，你有一辆车最多可以提供E的能量，你的车有四个档，最多换k次档
Assist Level 0 1 2 3
Assist Power 0 4 8 11
0档花费能量0，走的路程长度为0,1档花费1能量，走得最大路程为4…. ，每段路用一个档，如果这个档不能使你走完这段路，那么只能自己蹬，如果超过这段路长度，超过部分不计算到下一段路，意味着下一段路重算，问你蹬车的最短路程是多少？
解法：
最多1000段路，最多换10次档，最大提供能量为50，那么最多的状态为1000*10*50*4 =2e6，搜索所有状态的话2m也够，但是在搜索过程中肯定会挂掉很多状态，这些状态到中途夭折，所以能走到第n段路的状态肯定小于2e6，所以可以广搜，由此总结，可以用状态表示的都可以进行搜索枚举出来，只要状态少，在时间允许内，一般1e6，dp[i][k][e][l]=cost ,表示走到第i段路剩余k次机会，剩余e能量当前用的是l档的最短蹬车路程。

//UVAlive 6908

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
const int inf = 0x3f3f3f3f;
int n, k, e;
int a[maxn];
int dp[maxn][11][55][4];
bool vis[maxn][11][55][4];
int power[4] = {0, 4, 8, 11};
int ans;
struct node{
    int pos, k, e, l;
    node(){}
    node(int pos, int k, int e, int l) : pos(pos), k(k), e(e), l(l) {}
};

void bfs(){
    queue <node> q;
    memset(dp, inf, sizeof(dp));
    memset(vis, 0, sizeof(vis));
    dp[0][k][e][0] = 0;
    vis[0][k][e][0] = 1;
    q.push(node(0, k, e, 0));
    while(!q.empty()){
        node now = q.front(); q.pop();
        int &nowdp = dp[now.pos][now.k][now.e][now.l];
        if(now.pos == n){
            ans = min(ans, nowdp);
            continue;
        }
        if(now.k > 0){//还有换挡的机会&&换挡
            for(int i  = 0; i < 4; i++){
                if(i == now.l || now.e < i) continue;//可用能量小于花费肯定不行，不换挡的情况后面讨论
                node nxt = now;
                nxt.pos++; nxt.k--; nxt.e -= i; nxt.l = i;
                int &nxtdp = dp[nxt.pos][nxt.k][nxt.e][nxt.l];
                int cost = max(0, a[nxt.pos] - power[nxt.l]);
                if(nxtdp > nowdp + cost){
                    nxtdp = nowdp + cost;
                    if(!vis[nxt.pos][nxt.k][nxt.e][nxt.l]){
                        q.push(nxt);
                        vis[nxt.pos][nxt.k][nxt.e][nxt.l] = 1;
                    }
                }
            }
        }
        node nxt = now;
        nxt.pos++;
        if(nxt.e < nxt.l){//能量不够了，直接变成0 挡，不用花费，直接蹬
            nxt.k = 0, nxt.e = 0, nxt.l = 0;
        }
        else{
            nxt.k = now.k, nxt.l = now.l, nxt.e = now.e - now.l;
        }
        int cost = max(0, a[nxt.pos] - power[nxt.l]);
        int &nxtdp = dp[nxt.pos][nxt.k][nxt.e][nxt.l];
        if(nxtdp > nowdp + cost){
            nxtdp = nowdp + cost;
            if(!vis[nxt.pos][nxt.k][nxt.e][nxt.l]){
                q.push(nxt);
                vis[nxt.pos][nxt.k][nxt.e][nxt.l] = 1;
            }
        }
    }
}

int main()
{
    int T, ks = 0;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d%d", &n, &k, &e);
        for(int i = 1; i <= n; i++){
            scanf("%d", &a[i]);
        }
        ans = inf;
        bfs();
        printf("Case #%d: %d\n", ++ks, ans);
    }
    return 0;
}