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 |
不了解a single integer n的范围是多大啊,为啥偶把数组开成1都能过~优质dp留爪/**************************************************** 对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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator