正題

luogu 2803

---

題目大意

給出n個(gè)點(diǎn)，和相鄰的點(diǎn)的距離，每個(gè)點(diǎn)有一個(gè)權(quán)值，現(xiàn)在讓你建k個(gè)特殊點(diǎn)，使所有點(diǎn)到其中一個(gè)特殊點(diǎn)的代價(jià)之和最小

---

解題思路

先預(yù)處理處一個(gè)區(qū)間到同一個(gè)特殊點(diǎn)的最小代價(jià)

然后DP即可

–

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 111 using namespace std; int n, m, s[N], v[N], l[N], r[N], a[N][N], f[N][15]; int jsl(int x, int k) {return r[x] - r[k] - (s[k - 1] - s[x - 1]) * (v[n] - v[k]); } int jsr(int y, int k) {return l[y] - l[k] - (s[y] - s[k]) * v[k]; } int main() {scanf("%d%d", &n, &m);if (m >= n){puts("0");return 0;}for (int i = 1; i <= n; ++i){scanf("%d", &s[i]);s[i] += s[i - 1];}for (int i = 2; i <= n; ++i){scanf("%d", &v[i]);v[i] += v[i - 1];}for (int i = 1; i <= n; ++i)//處理前綴后綴{l[i] = (s[i] - s[i - 1]) * v[i];l[i] += l[i - 1];}for (int i = n; i > 0; --i){r[i] = (s[i] - s[i - 1]) * (v[n] - v[i]);r[i] += r[i + 1];}memset(a, 127/3, sizeof(a));memset(f, 127/3, sizeof(f));f[0][0] = 0;for (int i = 1; i <= n; ++i)for (int j = i; j <= n; ++j)for (int k = i; k <= j; ++k)a[i][j] = min(a[i][j], jsl(i, k) + jsr(j, k));//計(jì)算一個(gè)區(qū)間到同一個(gè)特殊點(diǎn)的最小代價(jià)for (int i = 1; i <= n; ++i)for (int j = 1; j <= i; ++j)for (int k = 1; k <= m; ++k)f[i][k] = min(f[i][k], f[j - 1][k - 1] + a[j][i]);//DPprintf("%d", f[n][m]);return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的【DP】建学校问题（luogu 2803/2018 特长生 T3）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。