Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:第一次自己推方程AC,顺便说说自己的思路。In Reply To:第一次自己推方程AC,顺便说说自己的思路。 Posted by:liushijian at 2010-03-12 19:44:56 > 留名纪念。 > 设b[i]=a[i]+a[i+1]+a[i+m-1],即按照题意把m个车厢合为一个。 > 即当m==2时。 > b[1]=a[1]+a[2],b[2]=a[2]+a[3]........以此类推。 > 所以就将此问题转换为01背包,也就是每个b[i]放于不放的问题。 > 由题可知背包大小为3,所以设DP[50001][3]; > 方程为 > dp[i][j]=max(dp[i-1][j],dp[k][j-1]+b[i]); > if(i-m<0) > k=0; > else > k=i-m; > i表示第几组b[i],j表示背包大小。 > 最后输出dp[n-m+1][3]即可。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator