CodeForces - 234 F. Fence DP

F. Fence

time limit per test

2 seconds

memory limit per test

256 megabytes

input

input.txt

output

output.txt

Vasya should paint a fence in front of his own cottage. The fence is a sequence of n wooden boards arranged in a single row. Each board is a 1 centimeter wide rectangle. Let's number the board fence using numbers 1, 2, ..., n from left to right. The height of the i-th board is hicentimeters.

Vasya has a 1 centimeter wide brush and the paint of two colors, red and green. Of course, the amount of the paint is limited. Vasya counted the area he can paint each of the colors. It turned out that he can not paint over a square centimeters of the fence red, and he can not paint over b square centimeters green. Each board of the fence should be painted exactly one of the two colors. Perhaps Vasya won't need one of the colors.

In addition, Vasya wants his fence to look smart. To do this, he should paint the fence so as to minimize the value that Vasya called the fence unattractiveness value. Vasya believes that two consecutive fence boards, painted different colors, look unattractive. The unattractiveness value of a fence is the total length of contact between the neighboring boards of various colors. To make the fence look nice, you need to minimize the value as low as possible. Your task is to find what is the minimum unattractiveness Vasya can get, if he paints his fence completely.

The picture shows the fence, where the heights of boards (from left to right) are 2,3,2,4,3,1. The first and the fifth boards are painted red, the others are painted green. The first and the second boards have contact length 2, the fourth and fifth boards have contact length 3, the fifth and the sixth have contact length 1. Therefore, the unattractiveness of the given painted fence is 2+3+1=6.

Input

The first line contains a single integer n (1 ≤ n ≤ 200) — the number of boards in Vasya's fence.

The second line contains two integers a and b (0 ≤ a, b ≤ 4·104) — the area that can be painted red and the area that can be painted green, correspondingly.

The third line contains a sequence of n integers h1, h2, ..., hn (1 ≤ hi ≤ 200) — the heights of the fence boards.

All numbers in the lines are separated by single spaces.

Output

Print a single number — the minimum unattractiveness value Vasya can get if he paints his fence completely. If it is impossible to do, print  - 1.

Examples

input

Copy

4
5 7
3 3 4 1

output

Copy

3

input

Copy

3
2 3
1 3 1

output

Copy

2

input

Copy

3
3 3
2 2 2

output

Copy

-1

题意：

给你n个木板，绿色染料a克，红色染料b克，一克染一厘米长度的木板且一个木板必须同一颜色，代价为相邻的两个木板挨着的不同的颜色的长度（厘米）的和，问最小代价？

分析：

dp[i][j][2]表示前i个木板，用了j个0/1燃料 （0：绿色，1：蓝色）的最小代价。

对于每一个木板分为染绿色和染红色两种进行状态转移，j的范围从h[i]到sum[i](sum[i]表示其前缀和）（因为对于当前的j他可以从0到sum[i-1]的所有状态转移过来）。

如果当前染绿色，则可以有上一个木板为绿色的转移过来或者上一个木板为红色的转移过来（红色的上一个状态的染料克=sum-j，绿色的染料确定，红色的开始确定)

dp[i][j][0]=min(dp[i-1][j-h[i]][0],dp[i-1][sum-j][1]+min(h[i],h[i-1]));

如果当前染绿色，同理

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long long ll ;
const int N=200+7;
int n,m,a,b,h[N];
int dp[N][40040][2];
//前i个木板，用了j个0/1燃料 ，0：绿色，1：蓝色
int main()
{
     freopen("input.txt","r",stdin);
     freopen("output.txt","w",stdout);
    scanf("%d",&n);
    scanf("%d%d",&a,&b);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&h[i]);
    }
    memset(dp,0x3f,sizeof(dp));
    dp[0][0][0]=0;
    dp[0][0][1]=0;
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        sum+=h[i];
        for(int j=h[i];j<=sum;j++)
        {
            if(j<=a)//染绿色
            {
                dp[i][j][0]=min(dp[i-1][j-h[i]][0],dp[i-1][sum-j][1]+min(h[i],h[i-1]));
            }
            if(j<=b)//染红色
            {
                dp[i][j][1]=min(dp[i-1][j-h[i]][1],dp[i-1][sum-j][0]+min(h[i],h[i-1]));
            }
        }
    }
    int ans=1e9;
    for(int i=1;i<=a;i++)
    {
        ans=min(ans,dp[n][i][0]);
    }
    for(int i=1;i<=b;i++)
    {
        ans=min(ans,dp[n][i][1]);
    }
    if(ans==1e9) ans=-1;
    printf("%d\n",ans);
    
    return 0 ;
}