網(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
