Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:第一次自己推方程AC,顺便说说自己的思路。

Posted by code_snail at 2010-07-29 16:15:46 on Problem 1976
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator