网易居然挂了我。。所以做一题网易的。。
https://www.nowcoder.com/question/next?pid=4575457&qid=83062&tid=7760015
dp+滚动数组+状态压缩
50w的数据让我们无法使用二维状态 50*50w也会报内存溢出
dp[i][j] i代表状态前置和后置状态 j代表两个塔的插值
我们把左边塔当作第一目标
所以j+height[i]当作往左边塔放入砖块
j-height当作右边塔放入砖块 右边塔放入时高度也会增加
如果不放入就用前置状态
三个求最大值
代码如下
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int dp[2][2*N]; //第一维滚动状态 第二维两个塔的差值
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;
}
现在的我是真的弱。。下周面网易游戏、头条、美团。。good luck and fighting
