Similar Subsequence
Accepted : Submit :
Time Limit : MS Memory Limit : KB Similar Subsequence For given sequence A=(a1,a2,…,an), a sequence S=(s1,s2,…,sn) has shape A if and only if: si=min{si,si+,…,sn} for all ai=;
si=max{si,si+,…,sn} for all ai=. Given sequence B=(b1,b2,…,bm), Bobo would like to know the number of subsequences of length n which have shape A modulo (+).
Input The input contains zero or more test cases and is terminated by end-of-file. For each test case: The first line contains two integers n and m. The second line contains n integers a1,a2,…,an. The thrid line contains m integers b1,b2,…,bm. The number of test cases does not exceed .
≤n≤
≤m≤
≤ai≤
≤bi≤m
b1,b2,…,bm are distinct. Output For each case, output an integer which denotes the number of subsequences modulo (+).
Sample Input Sample Output Note For the first sample, all three subsequences of length are of shape A. Source
XTU OnlineJudge /**
题目：Similar Subsequence
链接：http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1269
题意：给定A序列和B序列。A序列的数为0或1。 从B中取出一个长度和A相同的子序列S满足
si=min{si,si+1,…,sn} for all ai=0;
si=max{si,si+1,…,sn} for all ai=1. 问这样的S序列有多少种。结果mod 1e9+7;
个人分析过程：
显然要对A序列来处理。
假设最后一个是0，表明选的数，必须满足min{si,si+1,...,sn}。
那么如何确定B序列中的某个位置作为它。
最后一个数B序列任何位置皆可，无论a=0,1都可以满足min，max关系，因为只有它一个数。
倒数第二个数如何确认？
假设确定的最后一个数为x。
an-1 = 0; 那么这个数要比x小。
an-1 = 1; 那么这个数要比x大。 an-2 = 0; 那么这个数要比前面选过的数都小。
an-2 = 1; 那么这个数要比前面选过的数都大。
1: sn-2>sn-1
sn-1>x
sn = x;
sn-1<x
0: sn-2<sn-1 维护当前选好的序列中的最大和最小。
dp[i][j][k][flag]表示还要选i个数，当前选好的序列的最大值位置为j，最小值位置为k，
上一次选的位置为flag，flag=0表示为j位置，flag=1表示为k位置，的方法数。
因为：每次选了一个数后，位置一定是j或者k中的一个。
if(a[i]==0){ 通过flag来判断上次的选的位置，然后向前枚举遍历找一个满足<a[k]的位置pos； dp[i][j][k][flag] += dfs(i-1,j,pos,1);}
if(a[i]==1){ 通过flag来判断上次的选的位置，然后向前枚举遍历找一个满足>a[j]的位置pos； dp[i][j][k][flag] += dfs(i-1,pos,k,0);} if(i==0) return 1; 等一下：先试试对A序列从左到右考虑。 a1 = 0; 那么选择的第一个数为x必须满足B序列的x的右边比x大的数的集合为s,|s|>=n-1；
a1 = 1; 那么选择的第一个数为x必须满足B序列的x的右边比x小的数的集合为s,|s|>=n-1; a2 = 0；从前一个更新的集合s中，选择一个数，选择的x必须满足B序列的x的右边比x大的数的集合为s,|s|>=n-2； a3 = ？； 同理。 暂时不知怎么处理。 再回去试试从右往左考虑A序列。 正确思路：
在上面分析的基础上，由于时间超限了，对向前枚举遍历找一个满足<a[k]的位置pos；向前枚举遍历找一个满足>a[j]的位置pos；
这种操作优化一下。预处理mis[i]表示j<i, b[j]<b[i]的所有的j。mas[i]表示j<i, b[j]>b[i]的所有的j。
时间刚刚好卡过去了。。9000多ms。题目时限10s。 */ #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int maxn = 1e5+;
const int mod = 1e9+;
LL dp[][][][];
vector<int> mis[];///mis[i]表示j<i, b[j]<b[i]的所有的j。
vector<int> mas[505];///mas[i]表示j<i, b[j]>b[i]的所有的j。
int n, m;
int a[], b[];
void init()
{
for(int i = ; i <= m; i++){
mis[i].clear();
mas[i].clear();
}
for(int i = ; i <= m; i++){
for(int j = ; j < i; j++){
if(b[j]<b[i]){
mis[i].push_back(j);
}
if(b[j]>b[i]){
mas[i].push_back(j);
}
}
} }
LL dfs(int i,int j,int k,int flag)
{
if(i==) return ;
LL &res = dp[i][j][k][flag];
if(res!=-) return res;
res = ;
if(flag==){///j
if(j-<i) return res = ;
if(a[i]==){
/// j 的前面 比b[k]小的数。j<k；
int len = mis[k].size();
for(int d = ; d < len; d++){
if(mis[k][d]>=j) break;
res = (res+dfs(i-,j,mis[k][d],))%mod;
}
}else
{
int len = mas[j].size();
for(int d = ; d < len; d++){
res = (res+dfs(i-,mas[j][d],k,))%mod;
}
}
}else///k
{
if(k-<i) return res = ;
if(a[i]==){
int len = mis[k].size();
for(int d = ; d < len; d++){
res = (res+dfs(i-,j,mis[k][d],))%mod;
}
}else
{
int len = mas[j].size();
for(int d = ; d < len; d++){
if(mas[j][d]>=k) break;
res = (res+dfs(i-,mas[j][d],k,))%mod;
}
}
}
return res;
}
int main()
{
while(scanf("%d%d",&n,&m)==)
{
for(int i = ; i <= n; i++) scanf("%d",&a[i]);
for(int i = ; i <= m; i++) scanf("%d",&b[i]);
init();
memset(dp, -, sizeof dp);
LL ans = ;
for(int i = m; i >= n; i--){
ans += dfs(n-,i,i,);
ans %= mod;
}
printf("%I64d\n",ans%mod);
}
return ;
}