首页 > 代码库 > 两道很好的dp题目【4.29考试】
两道很好的dp题目【4.29考试】
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：
1 #include<cstdio> 2 int f[1005][1005],mod=1000000007; 3 int main() 4 { 5 freopen("B.in","r",stdin); 6 freopen("B.out","w",stdout); 7 char c;int i=1,ans=0; 8 c=getchar();f[1][1]=1; 9 while(c==‘D‘||c==‘I‘||c==‘?‘)10 {11 i++;12 for(int j=1;j<i;j++)13 f[i-1][j]=(f[i-1][j]+f[i-1][j-1])%mod;14 if(c==‘I‘){15 for(int j=2;j<=i;j++)16 f[i][j]=f[i-1][j-1];17 }18 if(c==‘D‘){19 for(int j=1;j<i;j++)20 f[i][j]=(f[i-1][i-1]-f[i-1][j-1]+mod)%mod;21 }22 if(c==‘?‘){23 for(int j=1;j<i;j++)24 f[i][j]=(f[i-1][i-1]-f[i-1][j-1]+mod)%mod;25 for(int j=2;j<=i;j++)26 f[i][j]=(f[i-1][j-1]+f[i][j])%mod;27 }28 c=getchar();29 }30 for(int j=1;j<=i;j++)31 ans=(ans+f[i][j])%mod;32 printf("%d",ans);return 0;33 }
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：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define ll long long 7 #define inf 2147483647 8 #define N 1005 9 #define mod 100000000710 using namespace std;11 int lcs[N][N],dp[N][N],ls[N][27];12 char a[N],b[N];13 void lalala(){14 int la=strlen(a+1),lb=strlen(b+1);15 for(int i=1;i<=la;i++)16 for(int j=1;j<=lb;j++){17 if(a[i]==b[j])lcs[i][j]=lcs[i-1][j-1]+1;18 else lcs[i][j]=max(lcs[i][j-1],lcs[i-1][j]);19 }20 }21 22 void nanana(){23 int lb=strlen(b+1);24 for(int i=1;i<=lb;i++){25 memcpy(ls[i],ls[i-1],sizeof(ls[i-1]));26 ls[i][b[i]-‘a‘+1]=i;27 }28 }29 30 int aaa(){31 int la=strlen(a+1),lb=strlen(b+1);32 for(int i=0;i<=la;i++)dp[i][0]=1;33 for(int j=0;j<=lb;j++)dp[0][j]=1; 34 for(int i=1;i<=la;i++)35 for(int j=1;j<=lb;j++){36 if(lcs[i-1][j]==lcs[i][j]){37 dp[i][j]+=dp[i-1][j];38 dp[i][j]%=mod;39 }40 int p=ls[j][a[i]-‘a‘+1];41 if(lcs[i][j]==lcs[i-1][p-1]+1&&p){42 dp[i][j]+=dp[i-1][p-1];43 dp[i][j]%=mod;44 }45 }46 return dp[la][lb];47 }48 49 int main(){50 freopen("C.in","r",stdin);51 freopen("C.out","w",stdout);52 scanf("%s",a+1);53 scanf("%s",b+1);54 lalala();55 nanana();56 printf("%d",aaa());57 return 0;58 }
两道很好的dp题目【4.29考试】