解题思路:从样例 1 2 3 4 5 可以看出 长度为n的一个非降序数组的子数组个数为 n(n+1) /2
因为,可以枚举子数组的长度,长度为1 时,有5种情况,为2时,12 、23、34、45,4种,为3时123、234、345,3种情况,为4时1234、2345,2种,为5时,1种情况,那么就是 5 + 4 + 3 + 2 + 1 = 15
得出等差数列的计算公式 n(n+1) /2
那么,我们只要遍历一遍数组,遇到 a[i] > a[i+1] 这种非降序情况时,算出前面非降序数组的子数组个数,然后继续遍历,把结果都加起来就是答案,注意子数组一定是连续的,从题中如果可以通过从开头和从结束分别删除若干个这句话可以得出。
不是算真子集个数。。。
#include<cstdio> #include<cmath> #include<algorithm> #include<string> #include<iostream> using namespace std; int a[100005]; long long f(long long x) { return (x+1)*x/2; } int main() { int n; scanf("%d",&n); for(int i=1; i<=n; ++i) scanf("%d",&a[i]); long long ans = 0; long long t = 0; //t表示非降序数组的起点位置的前一位 for(long long i=1; i<=n; ++i){ if(a[i]>a[i+1]||i==n){ ans += f(i-t); //i代表非降序数组的终点位置 t = i; //更新起点的前一位的位置 } } printf("%lld\n",ans); return 0; }