题目链接:https://ac.nowcoder.com/acm/contest/375/A
分析:我写的时候竟然把它当成了DP。。。。。。。
还建了个结构体DP数组,保存一二位,不知道当时脑子在抽啥。。。
事实上这题四重循环直接暴力就了过。。。。。。。
在大佬博客里学到了一种只用三重循环的高级做法
看看最后一重循环吧,因为是从后往前的,只有满足第四个条件,就把now+1,等在前面遇到满足第3个条件的数,此时now的数目就是其后满足第四个条件数的个数,直接加到ans上面即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=<<;
const double pi=acos(-);
const int mod=;
const int maxn=;
const int maxm=;
int a[maxn];
int main(){
int n;scanf("%d",&n);ll ans=;
for(int i=;i<=n;i++)scanf("%d",&a[i]);
for(int i=;i<=n-;i++){
for(int j=i+;j<=n-;j++){
if(a[j]>a[i]){
int now=;
for(int k=n;k>j;k--){//注意这里一定要从后往前
if(a[k]>a[j]) now++;
if(a[k]<a[j]&&a[k]>a[i]) ans+=now;
}
}
}
}
cout<<ans<<endl;
return ;
}