网站推广营销策划,做商城网站需要多大的服务器,个人网站做论坛,公司注册代理机构深圳文章目录题目描述解析代码题目描述 解析
#xff08;我觉得#xff09;很难的dp 思路是真的没有想出来 关键在于dp的设计#xff1a; dp[l][r]#xff1a;[l,r]的最小价值 f[l][r][a][b]#xff1a;把l到r之间除了数值在[a,b]之间的数全部消掉需要的最小价值 #xff08…
文章目录题目描述解析代码题目描述 解析
我觉得很难的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 pairll, 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 i1;in;i){// f[i][i][0][0]A;// for(int a1;am;a){// for(int ba;bm;b){// if(arank[i]brank[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]ab*(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]AB*(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
*/
