[R语言] UVALive 6908 Electric Bike dp

#include<bits/stdc++.h>
using namespace std;
int dp[1005][11][51][4][2];
int p[4]={0,4,8,11};
int a[1005];
int cas;
//第i个位置,j次换档,花了k，当前档为t
void solve(){
  int n,k,e;
  scanf("%d%d%d",&n,&k,&e);
  for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
  for(int i=0;i<1005;i++)
    for(int j=0;j<11;j++)
      for(int k=0;k<51;k++)
        for(int t=0;t<4;t++)
          for(int i2=0;i2<2;i2++)
            dp[i][j][k][t][i2]=1e9;
  dp[0][0][0][0][0]=0;
  dp[0][0][0][0][1]=0;
  for(int i=0;i<n;i++){
    for(int j=0;j<=k;j++){
      for(int K=0;K<=e;K++){
        for(int t=0;t<4;t++){
          for(int m=0;m<4;m++){
            dp[i+1][j][K][0][1]=min(dp[i+1][j][K][0][1],dp[i][j][K][t][0]+a[i+1]);
            dp[i+1][j][K][0][1]=min(dp[i+1][j][K][0][1],dp[i][j][K][0][1]+a[i+1]);
            if(t==m){
              if(K+m>e)
                dp[i+1][j][K][0][1]=min(dp[i+1][j][K][0][1],dp[i][j][K][t][0]+a[i+1]);
              else
                dp[i+1][j][K+m][m][0]=min(dp[i+1][j][K+m][m][0],dp[i][j][K][t][0]+max(0,a[i+1]-p[m]));
            }else{
              if(j==k){
                continue;
              }else if(K+m>e)
                dp[i+1][j+1][K][0][1]=min(dp[i+1][j+1][K][0][1],dp[i][j][K][t][0]+a[i+1]);
              else
                dp[i+1][j+1][K+m][m][0]=min(dp[i+1][j+1][K+m][m][0],dp[i][j][K][t][0]+max(0,a[i+1]-p[m]));
            }
          }
        }
      }
    }
  }
  int Ans = 1000000000;
  for(int j=0;j<=k;j++)
    for(int K=0;K<=e;K++)
      for(int t=0;t<4;t++)
        for(int i2=0;i2<2;i2++)
        Ans=min(Ans,dp[n][j][K][t][i2]);
  printf("Case #%d: %d\n",++cas,Ans);
}
int main(){
  int t;
  scanf("%d",&t);
  while(t--)solve();
  return 0;
}