本文主要是介绍AtCoder Beginner Contest 336 D - Pyramid，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
题意：就是给你一个长为n的序列，让你通过两种不限次数的操作 使其变为金字塔序列，(a1<a2<ak>ak-1>ak-2...>an)
两种操作分别是1：让任何一个数减一；2：去掉队头队尾
其实我们想这和最长连续上升（下降）有点关系，
dp[ i ]表示以i为结尾的最长上升长度
我们求出每个数的左右 最长连续序列即可
对于操作一其实没有什么影响，就相当于我们的常规的最长连续子序列的选与不选
对于2我们详细分析
1：a[ i -1 ]<a[ i] 这里到没什么特殊的就是和a[ i ] 这个限制取min
dp[ i ]=min(dp[ i-1 ]+1,a[ i ] );
2：a[ i-1 ]==a[ i ]
由于我们可以使数减一，我们可以让a[ i-1 ]的最长序列 减 1
举个例子 比如 :1 2 3 3
dp[4]=min(dp[3]+1,a[4])；
由于我们有a[4]的限制 ，相当于a[i-1]的最长序列就到 a[ 2 ],不论 a[2]是 1，还是2 ，3都会满足上式；
3：a[ i-1 ]>a[ i ]
同理与上
故状态转移方程就只有 dp[ i ]=min(dp[ i-1 ]+1,a[ i ] );
int a[N];
int dp1[N], dp2[N];
void solve()
{int n;cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];int ans = 0;for (int i = 1; i <= n; i++)dp1[i] = dp2[i] = 1;for (int i = 1; i <= n; i++){for (int j = 1; j < i; j++)if (a[j] < a[i])dp1[i] = max(dp1[i], dp1[j] + 1);}for (int i = n; i >= 1; i--){for (int j = n; j > i; j--){if (a[j] < a[i])dp2[i] = max(dp2[i], dp2[j] + 1);}}for (int i = 1; i <= n; i++)ans = max(ans, dp1[i] + dp2[i] - 1);cout << n - ans << endl;
}这篇关于AtCoder Beginner Contest 336 D - Pyramid的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
