hdu 6249 Alice’s Stamps DP

先删除所有被完全包含的区间。

然后对区间按照右端点排序。

dp[i][j]表示考虑前i个区间中选j个的最大覆盖面积。

然后三个转移。

dp[i][j] = dp[i – 1][j]

起传递作用

如果在i处有结尾的区间,长为l

dp[i][j] = dp[i – l][j – 1] + l

一个区间空当前区间

dp[i][j] = dp[loc[i – l + 1][j  -1] + (i – loc[i – l + 1])

一个区间 和当前区间相交。易证,直接取右端点最靠左的是最优解。

loc[i]表示右端点在i右侧,且离i最近的区间的右端点位置。预处理一下。

发表评论