HDU 2859 Phalanx——DP

网友投稿 706 2022-11-28

HDU 2859 Phalanx——DP

HDU 2859 Phalanx——DP

这题就是一道规律题, 可以发现对于对称矩阵对角线上的元素(i,j),他的上面所有元素(1~i, j)和他的右面所有元素(i, j~n)相匹配,设匹配数量为cnt,我们又可以发现(i,j)左下角的元素(i+1, j -1)的匹配数量一定为cnt+1,根据这个规律可以写出状态转移方程,具体过程请手动演算。

一开始计算匹配数量时一直优化不下来,总感觉是个O(n^3)的复杂度,无奈看了看别人的博客,发现都是我这种做法,于是干脆扔上了代码,暴力AC了

#include #include #include #include using namespace std;const int maxn = 1010;char s[maxn][maxn];int n, ans, dp[maxn][maxn];int main() { while (~scanf("%d", &n) && n) { for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1); ans = 1; for (int i = 1; i <= n; i++) { for (int j = n; j >= 1; j--) { if (i == 1 || j == n) { dp[i][j] = 1; continue; } int x = i, y = j; while (x >= 1 && y <= n && s[x][j] == s[i][y]) x--, y++; if (i - x >= dp[i - 1][j + 1] + 1) dp[i][j] = dp[i - 1][j + 1] + 1; else dp[i][j] = i - x; ans = max(ans, dp[i][j]); } } printf("%d\n", ans); } return 0;}

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:UVALive 7752 Free Figurines——双向链表
下一篇:使用ServletInputStream()输入流读取图片方式
相关文章

 发表评论

暂时没有评论,来抢沙发吧~