PTA 7-10 Hand-made Cream（8分）

• Input Specification
• Output Specification
• Sample Input
• Sample Output
• Hint
• 限制条件
• C++代码
• 运行结果

Suppose you are a baker planning to bake some hand-made cream breads.

To bake a cream bread, we need to use one slice of bread and one kind of cream. Each hand-made cream bread has a taste score to describe how delicious it is, which is obtained by multiplying the taste score for bread and the taste score for cream. (The taste scores could be negative, howerver, two negative tast scores can still produce delicious cream bread.)

The bread and cream are stored separately.

The constraint is that you need to examine the breads in a given order, and for each piece of bread, you have to decide immediately (without looking at the remaining breads) whether you would like to take it.

After you are finished with breads, you will take the same amount of cream in the same manner. The breads and creams you take will be paired in the same order as you take them.

Given N taste scores for bread and M taste scores for cream, you are supposed to calculate the maximum total taste scores for all hand-made cream bread.

Each input file contains one test case. For each case, the first line contains two integers N and M (1≤N,M≤10³ ), which are the numbers of bread and cream, respectively.

The second line gives N taste scores for bread.

The third line gives M taste scores for cream.

The taste scores are integers in [−10³,10³].

All the numbers in a line are separated by a space.

Print in a line the maximum total taste score.

3 4
-1 10 8
10 8 11 9

188

The maximum total taste score for the sample case is 10×10+8×11=188.

#include 

using namespace std;

int dp[1001][1001];

int main()
{
    int n, m;
    cin >> n >> m;

    int bread[1001];
    int cream[1001];

    int a;
    for(int i = 0; i < n; i++)
    {
        cin >> a;
        bread[i + 1] = a;
    }
    for(int i = 0; i < m; i++)
    {
        cin >> a;
        cream[i + 1] = a;
    }

    for(int i = 0; i <= n; i++)
    {
        dp[i][0] = 0;
    }
    for(int i = 0; i <= m; i++)
    {
        dp[0][i] = 0;
    }


    int result = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(dp[i - 1][j - 1] + bread[i] * cream[j] >= dp[i][j - 1] && dp[i - 1][j - 1] + bread[i] * cream[j] >= dp[i - 1][j])
            {
                dp[i][j] = dp[i - 1][j - 1] + bread[i] * cream[j];
            }
            else
            {
                if(dp[i][j - 1] > dp[i - 1][j])
                {
                    dp[i][j] = dp[i][j - 1];
                }
                else
                {
                    dp[i][j] = dp[i - 1][j];
                }
            }

            if(dp[i][j] > result)
            {
                result = dp[i][j];
            }
        }
    }
    cout << result;
    return 0;
}