本文主要是介绍[ACM] SDUT 2607 Mountain Subsequences，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Mountain Subsequences
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
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.
输入
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.
输出
示例输入
4abca
示例输出
4
提示
aba, aca, bca, abca
来源
示例程序
题意为给定长度为n的由小写字母组成的字符串，求有多少个字符串满足严格递增再递减。
比如 abca, 有 aba, aca , bca, abca ,四个符合题意的串。
注意acca，那么 aca ,aca算不同的串，因为c的下标不一样。
思路参考网上的。
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <cmath>
#include <stdlib.h>
#include <map>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <cctype>
using namespace std;
int n;
const int maxn=100010;
char s[maxn];
int dp[maxn];//dp[i]是以第i个字母结尾的递增子序列的个数（子序列的长度>=2)
int has[27];//has[i]是以字母'a'+i结尾的递增子序列的个数（子序列的长度>=1，等于1的情况就是它本身)
const int mod=2012;
//对于dp数组，枚举每个位置作为最高峰, 从左到右求一遍，再从右到左求一遍， 则以该位置作为最高峰符合题意的串
//的个数为 dp[i]*dp[i’] ， 最终答案为每个位置累加。 int main(int argc, char *argv[]) {while(scanf("%d",&n)!=EOF){scanf("%s",s);long long ans=0;memset(has,0,sizeof(has));for(int i=0;i<n;i++){int id=s[i]-'a';dp[i]=0;for(int j=0;j<id;j++){dp[i]+=has[j];dp[i]%=mod;}has[id]+=dp[i]+1;has[id]%=mod;}memset(has,0,sizeof(has));long long sum;//相当于上头的dp数组。 for(int i=n-1;i>=0;i--){int id=s[i]-'a';sum=0;for(int j=0;j<id;j++){sum+=has[j];sum%=mod;}has[id]+=sum+1;has[id]%=mod;ans+=sum*dp[i];ans%=mod;}cout<<ans<<endl;} return 0;
}
这篇关于[ACM] SDUT 2607 Mountain Subsequences的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
