http://poj.org/problem?id=3616

枚举区间左端点i,再枚举离左端点距离不小于R的右端点dp[j],更新dp[i]=max(dp[i], dp[j]+val[i])

/*32ms,224KB*/

const int mx = 1005;

p3 seg[mx];
map<int, int> mp;
int dp[mx];

int main()
{
    int n, m, rest, i, j, l, r, v;
    SIII(n, m, rest);
    For(i, m) SIII(l, r, v), seg[i] = MP(MP(l, r), v);
    sort(seg, seg + m);
    #define x first
    #define y second
 For(i, m) dp[i] = seg[i].y;
    Forr(i, 1, m) For(j, i) /// 由于右端点seg[j].x.y随j的变化没有单调性,所以要遍历一下
        if (seg[j].x.y <= seg[i].x.x - rest) dp[i] = max(dp[i], dp[j] + seg[i].y);
    PI(Max(dp, m));
    return 0;
}

Comments

comments powered by Disqus