第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛

78 阅读 0 评论 52 点赞

我是靠谱客的博主专一铃铛，最近开发中收集的这篇文章主要介绍第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

比赛链接

C题
对于子数组的定义，如果可以通过从开头和从结束分别删除若干个（可以为零或全部，前后删除个数不必相同）元素来从数组b获得数组a，则称数组a是数组b的子数组。（子数组包含原数组，但不包含空串）
即子数组是连续的
思路：一个非降序数组的所有子串都为非降序，只要把给定数组分为若干个非降序部分（每个部分要尽可能长），即从每个的地方断开，然后计算子串数，对于长度为n的数组子串数为，遍历然后相加。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100010;
int a[N], f[N];
int main()
{
int n;
cin >> n;
f[1] = 1;
long long ans = 0;
for(int i=1; i<= n; i++)
{
cin >> a[i];
f[i] = 1;
if(a[i] >= a[i-1] && i > 1)
f[i] = f[i-1] + 1;
ans += f[i];
}
cout << ans << endl;
return 0;
}