首页 > 其他 > 详细

POJ动态规划练习(计划6-8题)

时间:2016-07-22 20:56:40      阅读:302      评论:0      收藏:0      [点我收藏+]

Problems

POJ2192 - Zipper

 

Solutions

POJ2192 - Zipper

题目大意:给定字符串s1, s2和s,问s1和s2是否满足:均为s的子序列(不必连续)且恰能构成s?

用布尔变量 dp[i][j] 表示 s1 中前 i 个字符和 s2 中前 j 个字符能否构成 s 的前 i + j 个字符构成的子串 s‘,显然 s‘ 的最后一个字符只能是 s1[i] 和 s2[j] 中的一个,由此可以写出状态转移方程。边界条件为 dp[0][0] = 1。

技术分享
 1 //  Problem: poj2192 - Zipper
 2 //  Category: Dynamic programming
 3 //  Author: Niwatori
 4 //  Date: 2016/07/22
 5 
 6 #include <iostream>
 7 #include <cstring>
 8 #include <string>
 9 using namespace std;
10 
11 int main()
12 {
13     int t; cin >> t;
14     for (int i = 1; i <= t; ++i)
15     {
16         string s1, s2, s;
17         cin >> s1 >> s2 >> s;
18         int len1 = s1.length(), len2 = s2.length();
19         s1 =   + s1; s2 =   + s2; s = * + s;  // For convenience
20         
21         bool dp[205][205];
22         memset(dp, 0, sizeof(dp));
23         dp[0][0] = 1;
24         for (int i = 0; i <= len1; ++i)
25             for (int j = 0; j <= len2; ++j)
26             {
27                 if (s1[i] == s[i + j])
28                     dp[i][j] = dp[i][j] || dp[i - 1][j];
29                 if (s2[j] == s[i + j])
30                     dp[i][j] = dp[i][j] || dp[i][j - 1];
31             }
32         cout << "Data set " << i << ": " << (dp[len1][len2] ? "yes" : "no") << endl;
33     }
34     return 0;
35 }
View Code

 

POJ动态规划练习(计划6-8题)

原文:http://www.cnblogs.com/niwatori1217/p/5696939.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!