UVALive 6908---Electric Bike(DP或记录型深搜)

题目链接

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4920

problem  description

Two years ago, Putri bought an electric bike (e-bike). She likes e-bike a lot since it can assist her in cycling through steep roads when commuting to work. Over time, the battery capacity decreases. Now, her e-bike battery capacity is so low that she needs to carefully plan when to turn on the assist and at which level; different level of assist consumes different amount of energy and produces different assist power.

Putri divides the road that she travels from her home to her workplace into N segments where each segment has a steepness level. For example, the figure below shows a road with N = 7 segments.

             Segment     #1 #2 #3 #4 #5 #6 #7

             Steepness    10   3   0   1   2  15   9

From her home, Putri has to travel from the first road segment, to the second road segment, and so on, until the last segment to reach her work place. In the example above, the first segment has steepness of 10 which means Putri has to pedal her bike with 10 unit of energy. Her e-bike has fixed 4 assist levels where each level generates different power, as shown in the following table:

 Assist Level   0  1  2  3

            Assist Power  0  4  8  11

Assist level L will consume L unit of energy from the battery and will give Putri additional pedaling assist power according to the table above. Putri can only change the assist level to level L if the battery has at least L energy left and she is at the beginning of a road segment. Setting an assist level where the generated power is higher than the road steepness will cause the excess energy power to be wasted.

For example, if Putri sets the assist level L = 2 at the beginning of the first road segment (with steepness 10), then she only needs to pedal her bike with 2 unit of energy instead of 10 (since her ebike is assisting her with 8 unit of energy) to advance to the second road segment. If Putri sets the assist level L = 3, her e-bike generates more power to handle the steepness 10, thus she does not need to pedal at all, and the excess energy is wasted.

Putri can change the assist level instantly before entering a road segment, however, she does not want to change the assist level more than K times (it’s too tiring). If there is not enough energy in the battery to support the selected assist level for the road segment, the e-bike will shutdown at the beginning of the road segment and Putri has to pedal through the rest of the road segments, i.e. the assist level automatically set to 0 for the rest of the journey. Note that Putri can change her e-bike assist level (given it’s still less than K) at the beginning of the road segment to avoid shutdown by force. Initially at her home, the assist level is set to 0 and the battery is fully charged with E unit of energy. Putri wants to know the minimum energy she will need to pedal the bike to reach the workplace if she utilizes her e-bike optimally.

Input

The first line of input contains T (T ≤ 100) denoting the number of cases. Each case begins with three integers: N, K, and E in a line (1 ≤ N ≤ 1, 000; 0 ≤ K ≤ 10; 0 ≤ E ≤ 50) as described in the problem statement above. The next line contains N non-negative integers denoting the steepness level of i-th segment where i = 1 . . . N respectively. The steepness level of any road segment is at most 15.

Output

For each case, output ‘Case #X: Y ’, where X is the case number starts from 1 and Y is the minimum energy Putri needs to pedal the e-bike from her home to her workplace.

Explanation for 1st sample case:

Putri changes the assist level to 1 at (the beginning of) road segment #2, then change the assist level to 3 at road segment #6. Thus, she needs to pedal with 10 unit of energy for road segment #1 and 4 unit of energy for road segment #6. Note that if she changes the assist level to 1 at road segment #1 and then to assist level 3 at road segment #6, then at the beginning of road segment #7 the battery only has 2 unit of energy left and will automatically shutdown to assist level 0, thus Putri has to pedal with 9 energy for road segment #7.

Explanation for 2nd sample case:

Putri changes the assist level to 3 at road segment #1 and then changes to assist level 2 at road segment #2. Thus, she only needs to pedal 7 unit of energy for road segment #6 and 1 unit of energy for road segment #7.

Explanation for 3rd sample case:

Putri changes the assist level to 3 at road segment #1, then changes to assist level 1 at road segment #2, finally changes to assist level 3 at road segment #6. Thus, she only needs to pedal 4 unit of energy for road segment #6.

Sample Input

5

7 2 10

10 3 0 1 2 15 9

7 2 15

10 3 0 1 2 15 9

7 3 15

10 3 0 1 2 15 9

5 2 5

11 15 1 14 12

15 8 30

2 14 6 1 2 13 14 12 13 12 7 12 1 2 10

Sample Output

Case #1: 14

Case #2: 8

Case #3: 4

Case #4: 34

Case #5: 18

题意：一个人骑电动车去公司，电动车的初始电能是E，电动车有四个档位，0、1、2、3分别对应的输出能量是0、4、8、11 消耗的电能是对应的档位值大小。现在有n段路，每段路需要提供cost[i]的能量才能走过，如果在某一段路的档位对应的输出能量小于cost[i]，那么剩余的由这个人提供，如果电动车输出能量大于cost[i]，则多余部分浪费掉。现在电动车初始档位为0，求通过这条路且换挡不超过K次的情况下人提供的最小能量，注意：在某一段路时电动车的剩余电能小于当前的档位时，电动车报废，接下来的路由人提供能量；

思路：定义dp[i][j][k][f] 表示走到第i段路换了j次档电动车消耗k的电能，当前档位为f是人所消耗的能量；

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int inf=0x3f3f3f3f;
int dp[1005][12][60][4];
int d[4]={0,4,8,11};
int cost[1005];

int main()
{
    int T,Case=1,N,K,E;
    cin>>T;
    while(T--)
    {
        int ans=inf;
        scanf("%d%d%d",&N,&K,&E);
        for(int i=1;i<=N;i++)
            scanf("%d",&cost[i]);
        memset(dp,inf,sizeof(dp));
        dp[0][0][0][0]=0;
        for(int i=1;i<=N;i++)
        for(int j=0;j<=K;j++)
        for(int k=0;k<=E;k++)
        for(int s=0;s<4;s++)
        {
            if(k>=s)
            for(int p=0;p<4;p++)
            {
                if(s==p) dp[i][j][k][s]=min(dp[i][j][k][s],dp[i-1][j][k-s][p]+max(0,cost[i]-d[s]));
                else if(j>0) dp[i][j][k][s]=min(dp[i][j][k][s],dp[i-1][j-1][k-s][p]+max(0,cost[i]-d[s]));
                if(j==K&&s==0) dp[i][j][k][0]=min(dp[i][j][k][0],dp[i-1][j][k][p]+cost[i]);
                if(i==N) ans=min(ans,dp[i][j][k][s]);
            }
        }
        printf("Case #%d: %d\n",Case++,ans);
    }
    return 0;
}

还可以深搜：

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <map>
#include <bitset>
using namespace std;
typedef long long LL;
const int inf=0x3f3f3f3f;
int N,K,E;
int a[1005],sum[1005],p[4]={0,4,8,11};
int dp[1005][12][60][4];
bool vis[1005][12][60][4];

int calc(int pos,int k,int e,int f)
{
    if(pos==N+1) { return 0; }
    if(vis[pos][k][e][f]) return dp[pos][k][e][f];
    int Sum;
    if(e==0){
        Sum=sum[N]-sum[pos-1];
        vis[pos][k][e][f]=1;
        dp[pos][k][e][f]=Sum;
        return Sum;
    }
    
    int tmp=inf;
    for(int i=0;i<4;i++)
    {
        if(f!=i&&e>=i&&k>0){
            k--; e-=i; pos++;
            Sum=calc(pos,k,e,i)+max(0,a[pos-1]-p[i]);
            tmp=min(tmp,Sum);
            k++; e+=i; pos--;
        }
        else if(f==i&&e>=i){
            e-=i; pos++;
            Sum=calc(pos,k,e,f)+max(0,a[pos-1]-p[i]);
            tmp=min(tmp,Sum);
            e+=i; pos--;
        }
        else if(k==0&&e<f){
            Sum=sum[N]-sum[pos-1];
            vis[pos][k][e][f]=1;
            dp[pos][k][e][f]=Sum;
            return Sum;
        }
    }
    vis[pos][k][e][f]=1;
    dp[pos][k][e][f]=tmp;
    return tmp;
}
int main()
{
    int T,Case=1;
    cin>>T;
    while(T--)
    {
        sum[0]=0;
        scanf("%d%d%d",&N,&K,&E);
        for(int i=1;i<=N;i++)
        {
            scanf("%d",&a[i]);
            sum[i]=sum[i-1]+a[i];   
        }
        memset(vis,0,sizeof(vis));
        int u=calc(1,K,E,0);
        printf("Case #%d: %d\n",Case++,u);
    }
    return 0;
}