AcWing 1210. 连号区间数

2021-03-01 00:26

阅读：464

标签：get for href 思路 tar ret targe 循环区间dp

原题链接

考察:枚举

错误思路:

三层for循环暴力.

做多了区间dp...枚举区间只能想到按长度枚举区间,但这道题不能这么枚举.....

正确思路:

按区间端点来枚举区间,连号区间的特点是最大值-最小值 = 右端点-左端点.随着区间向右边延长,而动态记录最值.

 1 #include  2 #include 
 3 using namespace std;
 4 const int N = 10010;
 5 int a[N];
 6 int main()
 7 {
 8     int n,ans = 0;
 9     scanf("%d",&n);
10     for(int i=1;i"%d",&a[i]);
11     for(int i=1;i)
12     {
13         int maxn = 0,minv = N;
14         for(int j=i;j)
15         {
16             maxn = max(maxn,a[j]);
17             minv = min(minv,a[j]);
18             if(maxn-minv==j-i) ans++;
19         }
20     }
21     printf("%d\n",ans);
22     return 0;
23 }

AcWing 1210. 连号区间数

标签：get for href 思路 tar ret targe 循环区间dp

原文地址：https://www.cnblogs.com/newblg/p/14443283.html

上一篇：深度学习进度03（变量、api、案例：实现线性回归）

下一篇：WPF InkCanva中操作Stroke进行平移的方法

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing 1210. 连号区间数
文章链接：http://soscw.com/essay/58311.html

亲，登录后才可以留言！

AcWing 1210. 连号区间数

评论

热门文章

推荐文章

最新文章

置顶文章