A
问题描述：
对于一个排列，考虑相邻的两个元素，如果后面一个比前面一个大，表示这个位置是上升的，用I表示，反之这个位置是下降的，用D表示。如排列3,1,2,7,4,6,5可以表示为DIIDID。
现在给出一个长度为n-1的排列表示，问有多少种1到n的排列满足这种表示。
输入：
一个字符串S，S由I，D,？组成.？表示这个位置既可以为I，又可以为D。
输出：
有多少种排列满足上述字符串。输出排列数模1000000007
样例输入:
?D
样例输出：
3
数据范围：
20%的数据 S长度<=10
100%的数据 S长度<=1000
分析：怎么做？先想一想，i+1个数的方法数可以用i个数的方法数推出来，自然就想到了dp。一看数据范围，1000，只可以开二维，多半是二维dp。
dp[i][j] i表示共有i个数，j表示当前序列的最后一位为j。可以发现一个东西：前面i个数范围都在1~i且1~i中的每个数都只出现了1次。得出下列结论:
1.'D' 呈下降趋势，当前这位填j，前面那位可以填j+1~i-1(i表示序列长度，已经+1)，但这样的话，前面又有一个j，和当前这位j矛盾。我们可以视作前面所有>=j的数全部+1，来避免这种矛盾，所以当前位为j的前一位实际可以填j~i-1。(这一句重点)
2.'I' 呈上升趋势，当前这位填j，前一位填1~j-1的数。为什么不能填j?因为当前位填j后实际上整个序列是少一个为i(i表示序列长度，已经+1)的数的，我们只能把每个>=j的数视作+1来避免这种bug。如果当前位填j，前一位填j，前面那位会被视作+1，矛盾。
3.'？' D和I的情况加起来，耶。
解决。
CODE：
#include<cstdio>
int f[][],mod=;
int main()
{
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
char c;int i=,ans=;
c=getchar();f[][]=;
while(c=='D'||c=='I'||c=='?')
{
i++;
for(int j=;j<i;j++)
f[i-][j]=(f[i-][j]+f[i-][j-])%mod;
if(c=='I'){
for(int j=;j<=i;j++)
f[i][j]=f[i-][j-];
}
if(c=='D'){
for(int j=;j<i;j++)
f[i][j]=(f[i-][i-]-f[i-][j-]+mod)%mod;
}
if(c=='?'){
for(int j=;j<i;j++)
f[i][j]=(f[i-][i-]-f[i-][j-]+mod)%mod;
for(int j=;j<=i;j++)
f[i][j]=(f[i-][j-]+f[i][j])%mod;
}
c=getchar();
}
for(int j=;j<=i;j++)
ans=(ans+f[i][j])%mod;
printf("%d",ans);return ;
}
B
问题描述：
小A非常喜欢字符串，所以小K送给了小A两个字符串作为礼物。两个字符串分别为X，Y。小A非常开心，但在开心之余她还想考考小K。小A定义L为X与Y的最长公共子序列的长度（子序列在字符串内不一定连续，一个长度为L的字符串有2^L个子序列，包括空子序列）。现在小A取出了X的所有长度为L的子序列，并要求小K回答在这些子序列中，有多少个是Y的子序列。因为答案可能很大，所以小K只需要回答最终答案模10^9 + 7。
输入：
第一行包含一个非空字符串X。
第二行包含一个非空字符串Y。
字符串由小写英文字母构成。
输出：
对于每组测试数据输出一个整数，表示对应的答案。
样例输入：
aa
ab
样例输出：
2
数据范围：
对于20%的数据，1 <= |X|,|Y| <= 10
对于100%的数据，1 <= |X|,|Y| <= 1000
分析：一道很有趣的题，我没看出是dp
题目必须读懂，虽说是求a中所有长度为L的序列在b中出现的个数，其实就是求最大长度的lcs有多少种方法。。。cnm坑比题。知道这一点之后，dp方程也就不难想了。
由于范围是1000，所以只能开二维。dp[i][j]定义a中的前i个字符和b中的前j个字符构成的长度为 lcs（i，j）的公共子序列有多少种。
肯定先求lcs，每个位置的lcs都要求。然后dp怎么转移呢？由于是在a中取序列，只考虑a中的某位置的字符取还是不取。
1.如果不取当前这第i位的字符，且lcs[i][j]=lcs[i-1][j]，说明啥？说明了a中i位置这个字符对答案并无贡献，所以只用继承就可以。dp[i][j]+=dp[i-1][j]
2.取第i位字符。如果取了这个字符后，会有一个新的lcs长度刚好达到lcs[i][j]，那么这个位置的方法数也是可以加过来的。那么我们怎么表示新lcs的结尾在b中对应的是哪个字符（设为x,其最后位置为p）？预处理一下每个字符在b中出现的最后位置。为什么非要p，万一前面的x也可以构成新lcs呢？贪心，后面方法数的肯定比前面的方法数多，取p方法数一定最优。dp[i][j]+=dp[i-1][p-1]
PS：为什么这样做得到的一定是长度为lcs（a,b）的公共子序列，很有意思，lcs（a，b）中存的一定是最长lcs的长度，如果，只有长度满足才会递推过去，啊哈哈哈，啊哈哈哈。
完美解决,耶！
CODE：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
#define inf 2147483647
#define N 1005
#define mod 1000000007
using namespace std;
int lcs[N][N],dp[N][N],ls[N][];
char a[N],b[N];
void lalala(){
int la=strlen(a+),lb=strlen(b+);
for(int i=;i<=la;i++)
for(int j=;j<=lb;j++){
if(a[i]==b[j])lcs[i][j]=lcs[i-][j-]+;
else lcs[i][j]=max(lcs[i][j-],lcs[i-][j]);
}
} void nanana(){
int lb=strlen(b+);
for(int i=;i<=lb;i++){
memcpy(ls[i],ls[i-],sizeof(ls[i-]));
ls[i][b[i]-'a'+]=i;
}
} int aaa(){
int la=strlen(a+),lb=strlen(b+);
for(int i=;i<=la;i++)dp[i][]=;
for(int j=;j<=lb;j++)dp[][j]=;
for(int i=;i<=la;i++)
for(int j=;j<=lb;j++){
if(lcs[i-][j]==lcs[i][j]){
dp[i][j]+=dp[i-][j];
dp[i][j]%=mod;
}
int p=ls[j][a[i]-'a'+];
if(lcs[i][j]==lcs[i-][p-]+&&p){
dp[i][j]+=dp[i-][p-];
dp[i][j]%=mod;
}
}
return dp[la][lb];
} int main(){
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
scanf("%s",a+);
scanf("%s",b+);
lalala();
nanana();
printf("%d",aaa());
return ;
}