题解 | #取数游戏# 带滚动数组内存优化的dp

啊啊啊啊孩子出息了我们是第一

非常常规的滚动数组优化，要说有什么心思的话就是发现输入小于1000果断采用int16

#include <iostream>
#include <sys/types.h>
using namespace std;

int main() {
    int n,i,j,t,curi,previ;
    cin>>n;
    unsigned int dp[2][n+1],result=0;
    u_int16_t nums[2][n];
    for(j=0;j<2;++j)for(i=0;i<n;++i){
        cin>>nums[j][i];
       // cout<<nums[j][i]<<' ';
    }
    dp[0][0]=0;
    for(i=0;i<=n;++i){
        curi=i%2;
        previ=!curi;
        for(j=i?0:1;j<n-i+1;++j){//注意区分，ij是个数，不是下标
            t=i+j;//代表取的个数
            dp[curi][j]=max(i?dp[previ][j]+nums[1][t-1]*nums[0][i-1]:0,j?dp[curi][j-1]+nums[1][t-1]*nums[0][n-j]:0);
            result=max(dp[curi][j],result);
            //cout<<i<<' '<<j<<' '<<result<<endl;
        }
    }
    cout<<result<<endl;
}
// 64 位输出请用 printf("%lld")