杭电acm 1159,公共子序列问题,我的思路漏掉什么了啊?老是wrong answer网上有人说是动态规划,我怎么没看出来呢……(新手,对该算法还不太懂)我的思路是这样的:读入两个字符串A、B对A的每一
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/05 14:34:13
![杭电acm 1159,公共子序列问题,我的思路漏掉什么了啊?老是wrong answer网上有人说是动态规划,我怎么没看出来呢……(新手,对该算法还不太懂)我的思路是这样的:读入两个字符串A、B对A的每一](/uploads/image/z/10359280-64-0.jpg?t=%E6%9D%AD%E7%94%B5acm+1159%2C%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97%E9%97%AE%E9%A2%98%2C%E6%88%91%E7%9A%84%E6%80%9D%E8%B7%AF%E6%BC%8F%E6%8E%89%E4%BB%80%E4%B9%88%E4%BA%86%E5%95%8A%3F%E8%80%81%E6%98%AFwrong+answer%E7%BD%91%E4%B8%8A%E6%9C%89%E4%BA%BA%E8%AF%B4%E6%98%AF%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%2C%E6%88%91%E6%80%8E%E4%B9%88%E6%B2%A1%E7%9C%8B%E5%87%BA%E6%9D%A5%E5%91%A2%E2%80%A6%E2%80%A6%EF%BC%88%E6%96%B0%E6%89%8B%2C%E5%AF%B9%E8%AF%A5%E7%AE%97%E6%B3%95%E8%BF%98%E4%B8%8D%E5%A4%AA%E6%87%82%EF%BC%89%E6%88%91%E7%9A%84%E6%80%9D%E8%B7%AF%E6%98%AF%E8%BF%99%E6%A0%B7%E7%9A%84%EF%BC%9A%E8%AF%BB%E5%85%A5%E4%B8%A4%E4%B8%AA%E5%AD%97%E7%AC%A6%E4%B8%B2A%E3%80%81B%E5%AF%B9A%E7%9A%84%E6%AF%8F%E4%B8%80)
杭电acm 1159,公共子序列问题,我的思路漏掉什么了啊?老是wrong answer网上有人说是动态规划,我怎么没看出来呢……(新手,对该算法还不太懂)我的思路是这样的:读入两个字符串A、B对A的每一
杭电acm 1159,公共子序列问题,我的思路漏掉什么了啊?老是wrong answer
网上有人说是动态规划,我怎么没看出来呢……(新手,对该算法还不太懂)
我的思路是这样的:
读入两个字符串A、B
对A的每一个字符
在B里一个个字符匹配
匹配上的话
{公共子序列计数加1;记下B中这个位置,下次就从此处开始匹配;}
然后返回计数值(这就是以A为基准的公共子序列的长度)
然后把A、B位置调换,再做一遍以上过程,得到另一个计数值(以B为基准的)
将这两个值比较,较大的就是所求结果
我这样做测试用例都没问题,我又试了很多例子,也都对了,提交就是wrong answer,把数组扩大也不对,真不知哪里错了,
我的代码也搁这吧,可以结合着看一看
#include
using namespace std;
int sub(char a[1000],char b[1000])
{
int i,j;
int count = 0,find = -1;
for(i=0;a[i]!='\0';i++)
for(j=find+1;b[j]!='\0';j++)
{
if(a[i] == b[j])
{
count ++;
find = j;
break;
}
}
return count;
}
int main()
{
char a[1000],b[1000];
while(cin>>a>>b)
{
int x=sub(a,b),y=sub(b,a);
cout
杭电acm 1159,公共子序列问题,我的思路漏掉什么了啊?老是wrong answer网上有人说是动态规划,我怎么没看出来呢……(新手,对该算法还不太懂)我的思路是这样的:读入两个字符串A、B对A的每一
楼主的思路错了,你的代码我就不看了.
就是动态规划.
辅助空间变化示意图.
a b c f b c
a 1 1 1 1 1 1
b 1 2 2 2 2 2
f 1 2 2 3 3 3
c 1 2 3 3 3 4
a 1 2 3 3 3 4
b 1 2 3 3 4 4
子结构特征:
f(i,j)= 1. f(i-1,j-1)+1 (a[i]==b[j])
或者2. max(f(i-1,j),f(i,j-1)) (a[i]!=b[j])
由于f(i,j)只和f(i-1,j-1), f(i-1,j)和f(i,j-1)有关, 而在计算f(i,j)时, 只要选择一个合适的顺序, 就可以保证这三项都已经计算出来了, 这样就可以计算出f(i,j). 这样一直推到f(len(a),len(b))就得到所要求的解了.
我的AC代码.
#include
#include
#define max(a,b) a>b?a:b
int f[500][500];
int main()
{
char a[500],b[500];
int i,j;
int lena,lenb;
while(scanf("%s %s",a,b)!=EOF)
{
lena=strlen(a);
lenb=strlen(b);
for(i=0;i