Similar Subsequence Accepted : 10 Submit : 53 Time Limit : 10000 MS Memory Limit : 135536 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+1,…,sn} for all ai=0; si=max{si,si+1,…,sn} for all ai=1. Given sequence B=(b1,b2,…,bm), Bobo would like to know the number of subsequences of length n which have shape A modulo (109+7). 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 10. 1≤n≤20 1≤m≤500 0≤ai≤1 1≤bi≤m b1,b2,…,bm are distinct. Output For each case, output an integer which denotes the number of subsequences modulo (109+7). Sample Input 2 3 0 0 1 2 3 3 5 1 0 1 4 1 3 2 5 Sample Output 3 2 Note For the first sample, all three subsequences of length 2 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+100; const int mod = 1e9+7; LL dp[22][502][502][2]; vector<int> mis[505];///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[22], b[502]; void init() { for(int i = 1; i <= m; i++){ mis[i].clear(); mas[i].clear(); } for(int i = 1; i <= m; i++){ for(int j = 1; 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==0) return 1; LL &res = dp[i][j][k][flag]; if(res!=-1) return res; res = 0; if(flag==0){///j if(j-1<i) return res = 0; if(a[i]==0){ /// j 的前面 比b[k]小的数。j<k； int len = mis[k].size(); for(int d = 0; d < len; d++){ if(mis[k][d]>=j) break; res = (res+dfs(i-1,j,mis[k][d],1))%mod; } }else { int len = mas[j].size(); for(int d = 0; d < len; d++){ res = (res+dfs(i-1,mas[j][d],k,0))%mod; } } }else///k { if(k-1<i) return res = 0; if(a[i]==0){ int len = mis[k].size(); for(int d = 0; d < len; d++){ res = (res+dfs(i-1,j,mis[k][d],1))%mod; } }else { int len = mas[j].size(); for(int d = 0; d < len; d++){ if(mas[j][d]>=k) break; res = (res+dfs(i-1,mas[j][d],k,0))%mod; } } } return res; } int main() { while(scanf("%d%d",&n,&m)==2) { for(int i = 1; i <= n; i++) scanf("%d",&a[i]); for(int i = 1; i <= m; i++) scanf("%d",&b[i]); init(); memset(dp, -1, sizeof dp); LL ans = 0; for(int i = m; i >= n; i--){ ans += dfs(n-1,i,i,0); ans %= mod; } printf("%I64d ",ans%mod); } return 0; }