文章目錄

• 題目描述
• 解析
• 代碼

題目描述

解析

（我覺得）很難的dp
思路是真的沒有想出來
關鍵在于dp的設計：

dp[l][r]：[l,r]的最小價值
f[l][r][a][b]：把l到r之間除了數值在[a,b]之間的數全部消掉需要的最小價值

（為了本題要對數列離散化一下，f里的ab存的是數的按大小的編號）
關鍵在于這個f的設計
之后后面就好辦了，正常轉移即可

事后諸葛：
為什么想到這么設計ｆ呢？
因為這么能做出來
直觀一點的想的話，我們想要轉移，關鍵在于區間的最值
所以有此一想

代碼

（在代碼實現中，本人選擇用f[l][r][0][0]存dp答案）

#include <bits/stdc++.h> using namespace std; #define ll long long typedef pair<ll, ll> pr; const int N = 52; const int mod = 1e9 + 7; int n, m; int A, B; int w[N], q[N], rank[N]; ll dp[N][N], f[N][N][N][N]; int main() {memset(f, 0x3f, sizeof(f));scanf("%d%d%d", &n, &A, &B);for (int i = 1; i <= n; i++) scanf("%d", &w[i]), rank[i] = q[i] = w[i];sort(q + 1, q + 1 + n);int tot = unique(q + 1, q + 1 + n) - q - 1;for (int i = 1; i <= n; i++) rank[i] = lower_bound(q + 1, q + 1 + tot, rank[i]) - q;// for(int i=1;i<=n;i++){// f[i][i][0][0]=A;// for(int a=1;a<=m;a++){// for(int b=a;b<=m;b++){// if(a==rank[i]&&b==rank[i]) f[i][i][a][b]=0;// else f[i][i][a][b]=a;// }// }// }// printf("a=%d\n",a);for (int len = 1; len <= n; len++) {for (int l = 1; l + len - 1 <= n; l++) {int r = l + len - 1;f[l][r][0][0] = 2e9;for (int a = 1; a <= tot; a++) {for (int b = a; b <= tot; b++) {f[l][r][a][b] = 2e9;int tl = l, tr = r;while (w[tl] >= q[a] && w[tl] <= q[b]) tl++;while (w[tr] >= q[a] && w[tr] <= q[b]) tr--;if (tl > tr)f[l][r][a][b] = 0;else if (tl == tr)f[l][r][a][b] = A; // printf("ok,f=%d\n",f[l][r][a][b]);else {f[l][r][a][b] = min(f[tl][tr][0][0], f[tl][tr][a][b]);for (int mid = tl; mid < tr; mid++) {f[l][r][a][b] =min(f[l][r][a][b], f[tl][mid][a][b] + f[mid + 1][tr][a][b]);}}// if(f[l][r][0][0]>f[l][r][a][b]+a+b*(q[b]-q[a])*(q[b]-q[a]))// printf(" a=%d b=%d tl=%d tr=%d f=%d// val=%d\n",q[a],q[b],tl,tr,f[l][r][a][b],f[l][r][a][b]+A+B*(q[b]-q[a])*(q[b]-q[a]));f[l][r][0][0] = min(f[l][r][0][0], f[l][r][a][b] + A + B * (q[b] - q[a]) * (q[b] - q[a]));}}// printf("l=%d r=%d dp=%d\n",l,r,f[l][r][0][0]);}}printf("%lld\n", f[1][n][0][0]);return 0; } /* 10 3 1 7 10 9 10 6 7 10 7 1 2 */

總結

以上是生活随笔為你收集整理的最小代价（区间dp）（ybtoj）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。