HDU - 6024 B - Building Shops

線性DP

​​https://acm.dingbacode.com/showproblem.php?pid=6024​​

可以很簡單地 \(O(n^2)\) 預處理和，而我賽時犯傻了一直隻有 \(O(n^3)\) 的做法。然後遞推也想不明白。其實不建糖果店的方案隻要枚舉目前之前的每個點就可以了，用 \(dp[i][1]\) 記錄在 \(i\) 點放糖果店的代價，遞推：

\[ dp[i][1] = min(dp[i-1][0],dp[i-1][1]) + c[i] \\ dp[i][0] = min(dp[j][1] + sum[j][i])

\]

複雜度 \(O(n^2)\)

當時還因為數組開小了，一直 T ....蠢死我了...還以為是題壞了...果然RE一生鍋啊T T

點選檢視代碼

#include <algorithm>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 3e3 + 5;
const ll INF = 1e18;
const int mod = 1e9 + 7;


ll dp[N][2], sum[N][N];
int n;
struct node {
    int p, c;
    bool operator<(const node& r) { return p < r.p; }
} a[N];
int main() {
    while (cin >> n) {
        for (int i = 1; i <= n; i++) {
            cin >> a[i].p >> a[i].c;
        }

        sort(a + 1, a + 1 + n);

        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                sum[i][j] = sum[i][j - 1] + a[j].p - a[i].p;
            }
        }

        dp[1][1] = a[1].c;
        dp[1][0] = INF;
        for (int i = 2; i <= n; i++) {
            dp[i][1] = min(dp[i - 1][1], dp[i - 1][0]) + a[i].c;

            ll res = INF;
            for (int j = 1; j < i; j++) {
                res = min(res, dp[j][1] + sum[j][i]);
            }
            dp[i][0] = res;
        }
        // for (int i = 1; i <= n; i++) cout << dp[i][0] << " \n"[i == n];
        // for (int i = 1; i <= n; i++) cout << dp[i][1] << " \n"[i == n];
        cout << min(dp[n][1], dp[n][0]) << endl;
    }
}