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

坑爹啊,明明是贪心,害得我用dpA掉的,附dp思路

Posted by lijingwei at 2011-08-10 16:17:55 on Problem 2336
In Reply To:怎么放DP练习来了。。。。 Posted by:LMagic at 2010-07-29 05:24:49
核心代码,每次只看这个人是和前面几个人一起坐船(0~n-1),w表示等待时间
for(i=1;i<=m;i++)
{
        for(j=max(0,i-n);j<i;j++)//和前面0个人,1个人,。。。n-1个人一条船
	{
		temp=max(0,w[j]+2*t+a[j]-a[i]);//注意对w[0],a[0],cnt[0]赋值
		w[i]=min(w[i],temp);
		if(w[i]==temp)
		cnt[i]=min(cnt[i],cnt[j]+1);
	}
   //     cout<<i<<"   "<<a[i]+w[i]+t<<"   "<<cnt[i]<<endl;
}
外加全局变量和局部变量名字弄重了wa了一次,bs下自己。
然后对比网上ac代码测数据发现网上的有错
比如2 3 1
应该输出4竟然别人输出5的a了,数据不够强啊。

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