Welcome to 郁闷的外星猫's Blog.
阳光总在风雨后，不经历风雨怎能见得彩虹
Bless All~
Fly & High.For Future
Tomorrow,Valentine's Day,Lonely
作者:renqing 日期:2009-02-13
PKU1050 To the Max
作者:renqing 日期:2009-02-08
好吧，全当我无聊了。本来在那里copy homework，没事干打开Topcoder，发现有SRM，结果没有报名，遂决定不做Topcoder，去PKU且沏一道题，随便找了找，写了一道DP的题目.
好吧，我直接给出方程式:
f[i,j,k]=a[i,j-k+1]~a[i,j]
f[i,j,k]=max{f[i,j,k],f[i,j,k]+f[i-1,j,k]}
恩，就这些...一开始奇特的想出一个O(n^4)的DP方程，想了一想，估计可能TLE，所以就没写程序，直接写了一个O(n^3)的DP，Coding出来的程序，一次AC，很好- -|||唯一就是耗时32ms..
好吧，我直接给出方程式:
f[i,j,k]=a[i,j-k+1]~a[i,j]
f[i,j,k]=max{f[i,j,k],f[i,j,k]+f[i-1,j,k]}
恩，就这些...一开始奇特的想出一个O(n^4)的DP方程，想了一想，估计可能TLE，所以就没写程序，直接写了一个O(n^3)的DP，Coding出来的程序，一次AC，很好- -|||唯一就是耗时32ms..
