web analytics

POJ1692 Crossed Matchings DP

题目链接:http://poj.org/problem?id=1692

分析:

我们设f[i][j]表示在第一行选了i个数,第二行选了j个数的最大匹配数。

当我们在决策f[i][j]时

情况一:不匹配i f[i-1][j]

情况二:不匹配j f[i][j-1]

情况三:line_1[i]==line_2[j] 这个谁都不匹配

情况四:line_1[i]!=line_2[j]

这个时候我们需要在第一行找到一个离i最近的k1.k1要求line_1[k1]==line_2[j]

我们需要再找到一个里j最近的k2.k2要求line_2[k2]==line_2[i]

这样才能构成匹配。

匹配数就是 f[k1-1][k2-1]+2

 

Post a Comment

You must be logged in to post a comment.