西安网站seo公司,东莞市专注网站建设怎么样,郸城县做网站,桥头网站仿做这竟然是IOI虽然是2000年的#xff0c;但其实也改变不了它水题的本质 我写了两种方法#xff0c;这里都讲一下吧 考虑记忆化搜索#xff0c;用f[i][j]表示当区间的左端为i#xff0c;右端为j时最少要添加多少字符#xff0c;所以ans就为f[1][n] 然后考虑一下#xff0c;对… 这竟然是IOI虽然是2000年的但其实也改变不了它水题的本质 我写了两种方法这里都讲一下吧 考虑记忆化搜索用f[i][j]表示当区间的左端为i右端为j时最少要添加多少字符所以ans就为f[1][n] 然后考虑一下对于每一个f[i][j]都有转移 s[i]s[j]则有f[i][j]f[i1][j-1]s[i]!s[j] ,则有f[i][j]min(f[i1][j],f[i][j-1])(左右两边加一个字符看看那种情况更优)这里连枚举的顺序也懒得推了直接跑了个记忆化搜索就过了 CODE #includecstdio
#includecstring
using namespace std;
const int N5005;
short int f[N][N],n;
char s[N];
inline int min(int a,int b)
{return ab?a:b;
}
inline void DP(int l,int r)
{if (lr) { f[l][r]0; return; }if (s[l]s[r]){if (f[l1][r-1]-1) DP(l1,r-1);f[l][r]f[l1][r-1];} else{if (f[l1][r]-1) DP(l1,r);if (f[l][r-1]-1) DP(l,r-1);f[l][r]min(f[l1][r],f[l][r-1])1;}
}
int main()
{scanf(%d%s,n,s1);memset(f,-1,sizeof(f));DP(1,n);printf(%d,f[1][n]);return 0;
} 注意这里的内存问题开int的话都是要MLE的但是由于数据范围5000因此开short int足矣 还有一种算法就是很套路的了 我们很轻易的发现将原串倒过来之后他们的最长公共子序列LCS都是不用再添加字符的而对于其它的字符每个都要找一个字符与之相对应地匹配 证明不难这里省略了观察即可得出 LCS的DP方程也很简单用f[i][j]表示第一个串前i个字符第二个串前j个字符的LCS是多少转移有 s[i]s[j] f[i][j]f[i-1][j-1]1s[i]!s[j] f[i][j]max(f[i-1][j],f[i][j-1])(之前的决策二选一)是不是觉得和第一种的DP式有几分相似其实他们本质上也是一样的 所以又可以请出滚存来优化内存了 CODE #includeiostream
#includestring
using namespace std;
const int N5005;
int f[2][N],n;
string s1;
inline int max(int a,int b)
{return ab?a:b;
}
int main()
{int i,j;ios::sync_with_stdio(false);cinns1; string s2(s1.rbegin(),s1.rend());for (i0;in;i){int now(i1)1,lstnow^1;for (j0;jn;j)if (s1[i]s2[j]) f[now][j1]f[lst][j]1; else f[now][j1]max(f[lst][j1],f[now][j]);}coutn-f[n1][n]endl;return 0;
} 转载于:https://www.cnblogs.com/cjjsb/p/9029064.html
