题目描述

给你两个整数序列a和b，a长度为n，b长度为m。
请你求出两个长度相同的非空子序列（a中一个，b中一个），使其点积最大。

输入描述

第1行为n和m，第2行为a的n个数，第3行为b的m个数

输出描述

输出最大的点积

样例输入

4 3
2 1 -2 5
3 0 -6

样例输出

18

解释：a中选(2,-2)，b中选(3,-6)

代码

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int a[N],b[N];
int f[N][N],n,m; //f[i][j]为只从a数组的前i个和b数组的前j个中选的最大点积
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i];

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            //都选
            f[i][j]=max(0,f[i-1][j-1])+a[i]*b[j];
            //不选a[i]
            if(i>1) f[i][j]=max(f[i][j],f[i-1][j]);
            //不选b[j]
            if(j>1) f[i][j]=max(f[i][j],f[i][j-1]);
            printf("%d %d=%d\n",i,j,f[i][j]);
        }
    cout<<f[n][m];
    return 0;
}