6697专题

uvalive 6697 - Homework Evaluation - dp

题意:给出两个字符串,用第二个字符串去匹配第一个字符串,可以对第二个字符串进行删除或插入操作,一位匹配成功得8分失败-5分,如果插入或删除,对于连续插入或删除m个数减(4+m * 3)分。求最终得分的最大值。 用dp[i][j]表示第二个串的第i位和第一个串的第j位匹配得分的最大值,dp[i][j]可以是dp[i - 1][j - 1]继续匹配也可能是dp[i - 1][k]通过插入一段串得到或