dp[i]:以第i个字符为max，左边的可以构成的上升子序列的个数 。
dp2[i];以第i个字符为max，右边的可以构成的下降子序列的个数 。
num[i][j];在第i个位置以字符j为结尾的上升子序列的个数
num2[i][j];在第i个位置以字符j为开头的下降子序列的个数
很容易的推出状态转移：
int x=str[i-1]-'a';
for(j=0;j<26;j++)num[i][j]=num[i-1][j]%mod;
for(j=0;j<x;j++)num[i][x]+=num[i-1][j];
num[i][x]++;
num[i][x]%=mod;
dp[i]=0;
for(j=0;j<x;j++)dp[i]+=num[i-1][j];
dp[i]%=mod;
以此类推dp2[i],num2[i][j];
则ans=sigma((dp[i])*(dp2[i]));(1<=i<=n)
很显然，这道题目并不是很难。但是一定要注意，取余的时候对每一步都要取余。
不然很容易造成dp数组和num数组的越界。
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<stack>
using namespace std;
#define LL long long
#define maxn 110000
#define mod 2012
char str[maxn];
LL dp[maxn];
LL dp2[maxn];
LL num[maxn][27];
LL num2[maxn][27];
int main()
{// freopen("data1.in","r",stdin);int i,j,n;while(~scanf("%d",&n)){scanf("%s",str);memset(dp,0,sizeof(dp));memset(dp2,0,sizeof(dp2));memset(num,0,sizeof(num));memset(num2,0,sizeof(num2));for(i=1;i<=n;i++){int x=str[i-1]-'a';for(j=0;j<26;j++)num[i][j]=num[i-1][j]%mod;for(j=0;j<x;j++)num[i][x]+=num[i-1][j];num[i][x]++;num[i][x]%=mod;dp[i]=0;for(j=0;j<x;j++)dp[i]+=num[i-1][j];dp[i]%=mod;}for(i=n;i>=1;i--){int x=str[i-1]-'a';for(j=0;j<26;j++)num2[i][j]=num2[i+1][j]%mod;for(j=0;j<x;j++)num2[i][x]+=num2[i+1][j];num2[i][x]++;num2[i][x]%=mod;dp2[i]=0;for(j=0;j<x;j++)dp2[i]+=num2[i+1][j];dp[i]%=mod;}// cout<<endl;LL maxx=0;for(i=1;i<=n;i++){maxx+=(dp[i])*(dp2[i]);// maxx=maxx%mod;}cout<<maxx%mod<<endl;}return 0;
}