当前位置: 代码迷 >> 综合 >> CF #462 div C - A Twisty Movement
  详细解决方案

CF #462 div C - A Twisty Movement

热度:31   发布时间:2023-09-27 21:43:18.0

题目链接

CF #462 div C - A Twisty Movement

思路分析:

每次看到dp的题目,就很慌,其实慌是正常的,因为这些题目都不正常。

看到题目后: 1. 尽可能地分析题目,转换题目意思,得到隐藏的解决策略。

2. 找dp状态,和状态转换关系,然后dp方程求解。

其实第一步是挺不简单的,需要有观察法的思想。

先分析,既然数组只有1 和 2,那么最终一定会有一个断点 11111****22222** 这样的,

假如正解的答案是[l.r],那么断点应该是在这个区间的,如果在前面或者后面,那么这个翻转就没有意义。就等于是l == r,自己翻转自己,那么解就对应了前述的特殊情况。

问题来了 ,可以等价于找[1 , l-1] 的1的个数 + [l,r]的最长下降子序列长度 + [r+1 , n]的2的个数 ,做一堆预处理即可,中间区间的最长下降子序列才是dp的核心,注意优化哦!

#include<bits/stdc++.h>
using namespace std;
int dp[2005][2005],pre[2005],ord[2005],ans = 0;
int main(){int n,a[2005];scanf("%d",&n);for(int i = 1;i<=n;i++) scanf("%d",&a[i]);//预处理 l r 的 最长不上升长度memset(dp,0,sizeof(dp)); memset(pre,0,sizeof(pre));memset(ord,0,sizeof(ord));int cnt = 0;for(int i = 1;i<=n;i++){if(a[i] == 1) cnt++;pre[i+1] = cnt;}cnt = 0;for(int i = n;i>=1;i--){if(a[i] == 2) cnt++;ord[i-1] = cnt;}for(int i = 1;i<=n;i++){int M1 = 0,M2 = 0;for(int j = i;j<=n;j++){if(a[j] == 1) dp[i][j] = max(M1,M2) + 1,M1 = max(M1,dp[i][j]);else dp[i][j] = M2 + 1,M2 = max(M2,dp[i][j]);}}for(int i = 1;i<=n;i++)for(int j = i;j<=n;j++)ans = max(ans,pre[i] + ord[j] + dp[i][j]);printf("%d",ans);	
}