第 45 屆國際大學生程式設計競賽（ICPC）亞洲區域賽（昆明）(熱身賽)C-Statues

題意

有 n 個 位 置 ， 給 k 個 雕 像 ， 每 個 雕 像 都 有 一 個 位 置 和 大 小 ， 想 要 將 它 放 在 第 i 個 位 置 ， 需 花 費 x ? ∣ j ? i ∣ ， 有n個位置，給k個雕像，每個雕像都有一個位置和大小，想要將它放在第i個位置，需花費x*|j-i|， 有n個位置，給k個雕像，每個雕像都有一個位置和大小，想要將它放在第i個位置，需花費x?∣j?i∣，
將 這 些 雕 像 按 照 大 小 非 遞 減 排 列 ， 求 出 最 小 花 費 ， 將這些雕像按照大小非遞減排列，求出最小花費， 將這些雕像按照大小非遞減排列，求出最小花費，

思路

因 為 數 據 只 有 5000 ， 所 以 考 慮 O ( n 2 ) d p , 第 一 層 n ， 第 二 層 k ， 因為資料只有5000，所以考慮O(n^2)dp,第一層n，第二層k， 因為數據只有5000，所以考慮O(n2)dp,第一層n，第二層k，
首 先 排 序 ， 根 據 大 小 從 小 到 大 排 序 ， 首先排序，根據大小從小到大排序， 首先排序，根據大小從小到大排序，

設 f [ i ] [ j ] 表 示 前 i 個 位 置 放 了 j 個 雕 像 ， 則 考 慮 第 j 個 放 不 放 的 問 題 ？ 設f[i][j]表示前i個位置放了j個雕像，則考慮第j個放不放的問題？ 設f[i][j]表示前i個位置放了j個雕像，則考慮第j個放不放的問題？

• 放 ！ f [ i ] [ j ] = f [ i ? 1 ] [ j ? 1 ] + a [ j ] . x ? a b s ( i ? a [ j ] . p ) 放！f[i][j] =f[i-1][j-1]+a[j].x*abs(i-a[j].p) 放！f[i][j]=f[i?1][j?1]+a[j].x?abs(i?a[j].p)
• 不 放 ！ f [ i ] [ j ] = f [ i ? 1 ] [ j ] 不放！f[i][j] = f[i-1][j] 不放！f[i][j]=f[i?1][j]

則 狀 態 轉 移 為 ： 則狀態轉移為： 則狀態轉移為：
f [ i ] [ j ] = m i n ( f [ i ? 1 ] [ j ] , f [ i ? 1 ] [ j ? 1 ] + a [ j ] . x ? a b s ( a [ j ] . p ? i ) ) f[i][j]=min(f[i-1][j],f[i-1][j-1]+a[j].x*abs(a[j].p-i)) f[i][j]=min(f[i?1][j],f[i?1][j?1]+a[j].x?abs(a[j].p?i))

因 為 取 m i n ， 所 以 m e m s e t ( f , I N F , s i z e o f ( f ) ) ， 并 且 邊 界 f [ 0 ] [ 0 ] = 0 ， 因為取min，所以memset(f,INF,sizeof(f))，并且邊界f[0][0]=0， 因為取min，所以memset(f,INF,sizeof(f))，并且邊界f[0][0]=0，

復 雜 度 O ( n k ) ， 復雜度O(nk)， 復雜度O(nk)，

Code

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;

const int N = 5e3 + 10;
struct node {
    ll x, p;
}a[N];

bool cmp(node a, node b) {
    if(a.x == b.x) return a.p < b.p;
    return a.x < b.x;
}

ll f[N][N];

void solve() {
    int n, k; cin >> n >> k;
    for(int i = 1;i <= k; i++) cin >> a[i].p >> a[i].x;
    sort(a + 1, a + k + 1, cmp);
    for(int i = 0;i < N; i++) {
        for(int j = 0;j < N; j++) {
            f[i][j] = 1e18;
        }
    }
    f[0][0] = 0;
    for(int i = 1;i <= n; i++) {
        for(int j = 0;j <= min(i, k); j++) {
            f[i][j] = f[i - 1][j];
            if(j > 0) f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1ll * abs(i - a[j].p) * a[j].x);
        }
    }
    cout << f[n][k] << endl;
}

signed main() {
    solve();
}