網(wǎng)易居然掛了我。。所以做一題網(wǎng)易的。。
https://www.nowcoder.com/question/next?pid=4575457&qid=83062&tid=7760015
dp+滾動數(shù)組+狀態(tài)壓縮
50w的數(shù)據(jù)讓我們無法使用二維狀態(tài) 50*50w也會報內(nèi)存溢出
dp[i][j] i代表狀態(tài)前置和后置狀態(tài) j代表兩個塔的插值
我們把左邊塔當(dāng)作第一目標(biāo)
所以j+height[i]當(dāng)作往左邊塔放入磚塊
j-height當(dāng)作右邊塔放入磚塊 右邊塔放入時高度也會增加
如果不放入就用前置狀態(tài)
三個求最大值
代碼如下

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int dp[2][2*N]; //第一維滾動狀態(tài) 第二維兩個塔的差值
int height[55];
int main()
{
    int n;
    cout << 1e5;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &height[i]);
    }
    memset(dp, 0, sizeof(dp));
    int p = 0;

    for (int j = 0; j < 2*N; j++) dp[1-p][j] = INT_MIN; //保證第一次取不到
    dp[1-p][N] = 0;//入口
    for (int i = 1; i <= n; i++)
    {
        for (int j = height[i]; j < 2*N; j++)
        {
            dp[p][j] = max(dp[1-p][j-height[i]]+height[i], dp[1-p][j]); //放到右邊減小差距并增加塔高 以及不放入磚塊
        }
        for (int j = 0; j+height[i] < 2*N; j++)
        {
            dp[p][j] = max(dp[p][j], dp[1-p][j+height[i]]); //放到左邊增加差距
        }
        p = 1 - p;
    }
    if (dp[1-p][N]) cout << dp[1-p][N] << endl;
    else cout <<-1;
    return 0;
}

現(xiàn)在的我是真的弱。。下周面網(wǎng)易游戲、頭條、美團(tuán)。。good luck and fighting