[SRM] 08 B

B-3 SRM 08

描述

给长度为 n 的数列 A 和长度为 m 的数列 B，问有多少长度为 m 的数列 C 满足

$1 leq C_1<C_2<...<C_mleq n$

$(A_{c_1}+B_1) leq (A_{c_2}+B_2) leq ... leq (A_{c_m}+B_m)$

输入格式

第一行俩整数 n 和 m

第二行 n 个整数 $A_i$ ，表示数列 A

第三行 m 个整数 $B_i$ ，表示数列 B

输出格式

一个整数，表示满足条件的数列 C 的个数模 $10^9+7$ 后的值。

样例输入 1

5 3
1 5 2 4 7
7 9 6

样例输出 1

样例输入 2

4 2
7 7 7 7
3 4

样例输出 2

数据范围与约定

$1 leq A_i, B_i leq 10^9$
$1 leq m leq n$
$1 leq n leq 2000, 1leq m leq 1000$

样例解释

第一个样例中，数列 C 可以为 (1, 3, 5), (1, 4, 5), (2, 4, 5), (3, 4, 5)

第二个样例中，数列 C 可以为 (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)

分析

某渣表示毫无头绪... 感谢YY大佬提供代码orzYY。

看过YY大佬的代码才知道这是序列性DP。

序列DP都有个很明显的特征... 大序列的解继承自小序列。

那么我们用DP[j][i]表示当前最长序列以A[j]+B[i]作为最后一个元素时的方案数（解）。

那么遍历前面的A_i，看是否有一个A[k]+B[i-1]满足A[k]+B[i-1] 不大于 A[j]+B[i] （也就是说，当前这个末尾元素可以符合题意地补充进DP[k][i-1]，也就是前文所说的继承）

有的话，DP[j][i] += DP[k][i-1]（而之前已经预处理过使每一个 DP_j,i都为1了）。

关键点在于，A的下标“飘忽不定”，而B的下标是“稳步推进”的。

那么显然，A[k]的下标k根据题意，不可能小于i-1（因为A[k]与B[i-1]配对，k最少的情况是A与B一一配对，也就不可能少于i-1了）。那么k的范围确定为[ i-1 , j )

（当然YY神犇写[ 1 , j )也没错，评测通过）

对于i和j范围就是显然的了。

还有个点，最后的答案，只是DP[n][m]吗？

代码

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #define maxn 10000
 5 #define mod 1000000007
 6 using namespace std;
 7 
 8 int DP[maxn][maxn],A[maxn],B[maxn];
 9 int n,m;
10 
11 int main(){
12     int n,m;
13     scanf("%d%d",&n,&m);
14     
15     for(int i = 1;i <= n;i++){
16         scanf("%d",&A[i]);
17         DP[i][1] = 1;
18     }
19     
20     for(int i = 1;i <= m;i++)
21         scanf("%d",&B[i]);
22     
23     
24     for(int i = 2;i <= m;i++)
25         for(int j = i;j <= n;j++)
26             for(int k = i-1;k < j;k++)
27                 if(A[k]+B[i-1] <= A[j]+B[i])
28                     DP[j][i] = (DP[j][i]+DP[k][i-1])%mod;
29                         
30     int ans = 0;
31     
32     for(int i = m;i <= n;i++) ans = (ans+DP[i][m])%mod;
33                         
34     printf("%d",ans);                    
35     
36     return 0;
37 }

推荐不看= =

转载请注明出处 -- 如有意见欢迎评论