[DP][线段树][离散化][细节][坑] XDOJ 1324

离散化写挫了就wa了n发。。

先按照右端点排序,设dp[i]为铺满1到i的最小价值,注意是铺满,那么就可以在这里更新dp[r[i]]=min(dp[j])+v[i]  l[i]<=j<=r[i],注意这里有一个-1,对于左端点来说,因为如果两个线段相邻二不相交,比如(1,2)(3,4),这样其实也是可以的。这里的话,如果直接把端点离散化,就会导致后面的操作很复杂,因为要考虑相邻中间有没有空(我也是这么错的),所以不如直接在一开始读入左端点的时候就给他-1,这样之后就不用什么多余的操作了,直接每次线段树查询最小值即可。

另外一个是为什么这个dp策略是正确的:这里能保证正确的原因完全是因为,给定的所有线段的最右端点都小于等于E,也就是说要么不能覆盖到,要么一定至少有1个地毯可以覆盖且刚好覆盖到E,所以只需要使状态为铺满1到i就可以了,虽然这其中一些点的dp值对于其意义来说是错误的,但是对于最后这个E却是一定正确的!

 


//#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
#define eps (1e-9)
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
const int INF=0x4f4f4f4f;

void read(int &x)
{
    char ch = getchar();
    x = 0;
    for (; ch < '0' || ch > '9'; ch = getchar());
    for (; ch >='0' && ch <= '9'; ch = getchar())
        x = x * 10 + ch - '0';
}

struct seg
{
    int i,flag;
    LL pos;
    bool operator<(const struct seg& rhs)const
    {
        return pos
	

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据