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

按block的最大高度排序,然后套多重背包模板即可,注意动态修改背包容量上限

/*172ms,356KB*/
#define x first
#define y second
#define MT(a, b, c) make_pair(a, make_pair(b, c))
const int mxw = 40005;

pair<int, pair<int, int> > p[405];
int dp[mxw], deq[mxw], deqv[mxw];

int solve(int maxw, int n)
{
    int i, a, j, s, t, val;
    For(i, n) For(a, p[i].y.x) ///枚举a=j%w[i]
 {
        s = t = 0; ///deque的头和尾
     for (j = 0; j * p[i].y.x + a <= p[i].x; ++j) /// 此题唯一需要注意的地方就是动态修改背包的容量上限
     {
            val = dp[j * p[i].y.x + a] - j * p[i].y.x ; ///划归为可重复使用的值
         while (t > s && deqv[t - 1] <= val) --t; ///保证deque的队首是最大的
         deq[t] = j;
            deqv[t++] = val;
            dp[j * p[i].y.x + a] = deqv[s] + j * p[i].y.x ; ///从双端队列的头部取出最大值
         if (deq[s] == j - p[i].y.y) ++s; ///这一头部已无法使用
     }
    }
    return Max(dp, maxw);
}

int main()
{
    int n, i, h, a, c;
    SI(n);
    For(i, n) SIII(h, a, c), p[i] = MT(a, h, c);
    sort(p, p + n);
    PI(solve(40000, n));
    return 0;
}

Comments

comments powered by Disqus