题目链接：http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2607
Mountain Subsequences
Problem Description
Coco is a beautiful ACMer girl living in a very beautiful mountain. There are many trees and flowers on the mountain, and there are many animals and birds also. Coco like the mountain so much that she now name some letter sequences as Mountain Subsequences.
A Mountain Subsequence is defined as following:
1. If the length of the subsequence is n, there should be a max value letter, and the subsequence should like this, a1 < ...< ai < ai+1 < Amax > aj > aj+1 > ... > an
2. It should have at least 3 elements, and in the left of the max value letter there should have at least one element, the same as in the right.
3. The value of the letter is the ASCII value.
Given a letter sequence, Coco wants to know how many Mountain Subsequences exist.
Input
For each case there is a number n (1<= n <= 100000) which means the length of the letter sequence in the first line, and the next line contains the letter sequence.
Please note that the letter sequence only contain lowercase letters.
Output
Example Input
4abca
Example Output
4
Hint
aba, aca, bca, abca
Author
题目链接：http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2607
题目大意：
给你一个长度为n的字符串仅由小写英文字母组成，求满足
a1 < ...< ai < ai+1 < Amax > aj > aj+1 > ... > an
的子串的个数,其实也就是统计所有满足以某一元素为中心左边递增，右边递减的子串的数目，要求该子串
最小长度为3，中心元素左右都至少有一个元素。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 100005;
const int mod = 2012;
char s[maxn];
int a[maxn], dp1[maxn], dp2[maxn], num[maxn];
//dp1[i]表示字符串1到i中以s[i]为结尾的递增子序列个数
//dp2[i]表示字符串i到n中以s[i]为结尾的递减子序列个数
int main()
{int n;while(cin >> n){scanf("%s", s+1);memset(dp1, 0, sizeof(dp1));memset(dp2, 0, sizeof(dp2));memset(num, 0, sizeof(num));for(int i = 1; i <= n; i++)a[i] = s[i] - 'a';for(int i = 1; i <= n; i++){for(int j = 0; j < a[i]; j++)dp1[i] = (dp1[i] + num[j]) % mod;//num[j]表示当前以s[j+'a']结尾的递增子序列个数num[a[i]] = (num[a[i]] + dp1[i] + 1) % mod;//当前以a[i]结尾的递增子序列加上因为此次a[i]出现而//新增的递增子序列个数，+1是因为a[j]自己也是一个递增的子序列}memset(num, 0, sizeof(num));for(int i = n; i >= 1; i--){for(int j = 0; j < a[i]; j++)dp2[i] = (dp2[i] + num[j]) % mod;num[a[i]] = (num[a[i]] + dp2[i] + 1) % mod;}int ans = 0;for(int i = 1; i <= n; i++)ans = (ans + dp1[i]*dp2[i]) % mod;cout << ans << endl;}return 0;
}