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

不了解a single integer n的范围是多大啊,为啥偶把数组开成1都能过~优质dp留爪

Posted by rayafjyblue at 2011-07-25 10:55:02 on Problem 2047 and last updated at 2011-07-25 10:59:04
/****************************************************
对n个节点按结束时间排序
dp[i][j]表示第一个房间到第i天,第二天房间到第j天的最优情况
对第i场音乐会取或不取
1.不取,
dp[j][k] = dp[j - 1][k],
dp[k][j] = dp[k][j - 1];
(a[i - 1].ed + 1 <= j <= a[i].ed, 1 <= k <= a[i].ed)
2.取,
dp[a[i].ed][j] = max(dp[a[i].ed][j], dp[a[i].st - 1][j] + a[i].val);
dp[j][a[i].ed] = max(dp[j][a[i].ed], dp[j][a[i].st - 1] + a[i].val);
(0 <= j <= a[i].ed)为保证无后效性,此循环倒过来写
发现完全就是01背包一个复杂化的版本~
****************************************************/
(>^ω^<)喵~
再用最小费用最大流水水看~~

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