[THUSC2016]成绩单

luogu P5336

description

每次可以选择连续一段，删掉，两边合并过来。删一段的代价为\(a+b*(max[l..r]-min[l...r])^2\)
\(n<=50\)

solution

这种带区间拼接合并，而且\(n\)很小的的，容易想到区间dp
\(f[l][r][x][y]\)表示使\([l,r]\)中最小值为\(x\),最大值为\(y\)的最小代价。

思路1

通常决策考虑第一个或最后一个的选取情况。我喜欢考虑最后一个（\(r\)）

留下
\(f[l][r][min(x,w_r)][max(y,w_r)]=f[l][r-1][x][y]\)
删
枚举划分点，右边删，左边留。
\(f[l][r][x][y]=min(f[l][k][x][y]+g[k+1][r])\)
我们发现\([k+1,r]\)不需要考虑max,min只需代价最小。因此令\(g[l][r]\)表示\([l,r]\)删完的最小代价。
\(g[l][r]=min(f[l][r][x][y])\)

思路1 code

点击查看代码

#include<bits/stdc++.h>using namespace std;const int N=55;int w[N],g[N][N],f[N][N][N][N],val[N];int main() {int n,a,b;scanf("%d%d%d",&n,&a,&b);for(int i=1;i<=n;i++)scanf("%d",&w[i]),val[i]=w[i];sort(val+1,val+1+n);int m=unique(val+1,val+1+n)-val;for(int i=1;i<=n;i++)w[i]=lower_bound(val+1,val+m,w[i])-val;memset(f,0x3f,sizeof(f));memset(g,0x3f,sizeof(g));for(int i=1;i<=n;i++)g[i][i]=a,f[i][i][w[i]][w[i]]=0;for(int l=n;l;l--) {for(int r=l+1;r<=n;r++) {for(int x=1;x<m;x++) {for(int y=1;y<m;y++) {f[l][r][min(x,w[r])][max(y,w[r])]=min(f[l][r][min(x,w[r])][max(y,w[r])],f[l][r-1][x][y]);for(int k=l;k<r;k++) {f[l][r][x][y]=min(f[l][r][x][y],f[l][k][x][y]+g[k+1][r]);}}}for(int x=1;x<m;x++)for(int y=1;y<m;y++)g[l][r]=min(g[l][r],f[l][r][x][y]+a+b*(val[y]-val[x])*(val[y]-val[x]));}}printf("%d",g[1][n]);return 0;}

思路2

\(g\)还是一样的要定义。
这个要直率的多，直接考虑所有情况。

删左半边
删右半边
两边都不删，因此两个\(f\)的3，4维都分别要是\(x,y\)
略

免责声明：本网信息来自于互联网，目的在于传递更多信息，并不代表本网赞同其观点。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，并请自行核实相关内容。本站不承担此类作品侵权行为的直接责任及连带责任。如若本网有任何内容侵犯您的权益，请及时联系我们，本站将会在24小时内处理完毕。