上海金马五校DHU(Ball Game)

Description

There are 4 types of balls (A, B, C and D) and a huge box. The balls of the same type have the same weight.

Lily likes to play a game. She puts theses balls into the box one by one. Suppose she has already put some balls into the box and their total weight is w. When she continues putting a new ball into the box, she will receive a bonus score, denoted as c. The value of c equals to the product of the weight of the new ball and the last digit of w. Note that when the box is empty, the value of w is 0.

Now give you the number of each type of balls and their weights, can you tell Lily the maximum score she can get in total?

Input

There are several test cases. Each test case has one line containing 8 numbers.

Each of the first 4 numbers, A, B, C and D (0 ≤ A, B, C, D ≤ 30), indicates the number of the respective type of balls.

Each of the next 4 numbers, a, b, c and d (1 ≤ a, b, c, d ≤ 100,000), indicates the weight of the respective type of balls.

Output

For each test case, print one line with the maximum total score Lily can get.

Sample Input

1 1 1 1 2 3 4 5
3 6 8 8 25 66 18 12

Sample Output

71
5213

Author: Alez

四维dp。。。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
int dp[50][50][50][50];
int wA,wB,wC,wD;
int fun(int a,int b,int c,int d)
{
    return a*wA+b*wB+c*wC+d*wD;
}
int main()
{
    int cntA,cntB,cntC,cntD;
 
    while(cin>>cntA>>cntB>>cntC>>cntD)
    {
        memset(dp,0,sizeof(dp));
        cin>>wA>>wB>>wC>>wD;
        for(int i=0;i<=cntA;i++)
        {
            for(int j=0;j<=cntB;j++)
            {
                for(int k=0;k<=cntC;k++)
                {
                    for(int l=0;l<=cntD;l++)
                    {
                        if(i>0)
                        dp[i][j][k][l]=max(dp[i-1][j][k][l]+((fun(i-1,j,k,l))%10)*wA,dp[i][j][k][l]);
                        if(j>0)
                        dp[i][j][k][l]=max(dp[i][j-1][k][l]+((fun(i,j-1,k,l))%10)*wB,dp[i][j][k][l]);
                        if(k>0)
                        dp[i][j][k][l]=max(dp[i][j][k-1][l]+((fun(i,j,k-1,l))%10)*wC,dp[i][j][k][l]);
                        if(l>0)
                        dp[i][j][k][l]=max(dp[i][j][k][l-1]+((fun(i,j,k,l-1))%10)*wD,dp[i][j][k][l]);
                    }
                }
            }
        }
        cout<<dp[cntA][cntB][cntC][cntD]<<endl;
    }
    return 0;
}