P5095 [USACO12OPEN]Bookshelf S

_xbn · 2021-05-18 20:15:48 · 题解

很显然此题要用动态规划，我们设 f(i) 表示当前到第 i 本书， 书架的最小高度。

接下来考虑转移，转移我们可以分两种情况讨论，第一，对于当前这本书，我们要新开一个书架，那么 f(i) = f(i-1) + h(i)，第二，我们选择把当前这本书插入之前的书架，那么我们就要知道前面书的最大高度，我们可以开一重循环寻找之前的最大高度，用它来更新当前状态 f(i) = min(f(i),f(j-1) + maxn)。

#include <bits/stdc++.h>
using namespace std;
const int N = 2002;
int n, m, p, k, ans, sum, tot, cnt, a[N], b[N], f[N], c[N], l;
int main()
{
    std::cin>> n >> l;
    for(int i = 1; i <= n; i++)
    {
        std::cin >> a[i] >> b[i];
        c[i] = c[i - 1] + b[i];
        f[i] = 1e9;
    }
    for(int i = 1; i <= n; i++)
    {
        f[i] = f[i - 1] + a[i];
        tot = a[i];
        for(int j = i - 1; j >= 1; j--)
        {
            if(c[i] - c[j - 1] > l)break;
            tot = max(tot, a[j]);
            f[i] = min(f[i], f[j - 1] + tot);
        }
    }
    cout << f[n];
    return 0;
}