[BZOJ2616][Thu Summer Camp2016]成绩单

一时失言乱红尘 2021-09-30 12:58 331阅读 0赞

[BZOJ传送门][BZOJ]

### 简易题意 ###

现在有一列数，有$n$个元素。每次操作选择一个连续的区间，删除它，代价为$a+b\\times (max-min)^2$，其中$max$和$min$表示这段区间的最大值和最小值。

### 数据范围 ###

$n\\leq50,a\\leq100,b\\leq10,w\_i\\leq1000$

## 题解 ##

这题第一眼是一个区间DP，$dp\_\{l,r\}$表示区间$\[l,r\]$被删去的最小代价。

然而菜鸡的我并不会区间DP。

于是我们我们可以想到把区间DP转化为序列DP。

具体的，我们倒序枚举$l$，之后顺序枚举$r$，每次往决策区间里面添加一个数(在本次操作中被删除)或添加一个整段区间(在之前的某次操作中被删除)。

对于每个确定的$l$，我们设$dp'\_\{r,v1,v2\}$表示当前确定到了第$r$个数，当前决策区间(此次删除的数)中最大值为$v1$，最小值为$v2$的最小代价。

显而易见,$dp\_\{l,r\}=min\\\{dp'\_\{r,v1,v2\}+b\\times calc(v1,v2)+a\\\}$。

(其中$v1,v2$需枚举)。

对于每个$dp'$的转移，我们可以使用类似背包的东西。

具体的，$dp'\_\{r,v1,v2\}$可以被用来更新$dp'\_\{r+1,max(v1,w\_\{r+1\}),min(v2,w\_\{r+1\})\}$，以及$dp'\_\{k,v1,v2\}$。

我们可以写出如下转移式(dp数组需要取最小值)。

$$  
dp'\_\{r+1,max(v1,w\_\{r+1\}),min(v2,w\_\{r+1\})\}=dp'\_\{r,v1,v2\}  
$$

$$  
dp'\_\{k,v1,v2\}=dp'\_\{r,v1,v2\}+dp\_\{r+1,k\}  
$$

之后输出$dp\_\{1,n\}$作为答案即可。

权值我们可以使用离散化来保证数组大小在$50$以内。

## 代码 ##

#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; template<typename __T> inline void read(__T &x) { x=0; int f=1;char c=getchar(); while(!isdigit(c)){if(c=='-') f=-1;c=getchar();} while(isdigit(c)) {x=x*10+c-'0';c=getchar();} x*=f; } int n,a,b; int hs[55],tot=0; int s[55]; int dp[55][55]; int ndp[55][55][55]; int ca(int a,int b) { return (a-b)*(a-b); } int main() { read(n); read(a); read(b); for(int i=1;i<=n;i++) { read(s[i]); hs[tot++]=s[i]; } sort(hs,hs+tot); tot=unique(hs,hs+tot)-hs; for(int i=1;i<=n;i++) s[i]=lower_bound(hs,hs+tot,s[i])-hs; memset(dp,63,sizeof(dp)); for(int l=n;l>=1;l--) { dp[l][l]=a; memset(ndp,63,sizeof(ndp)); ndp[l][s[l]][s[l]]=0; for(int r=l;r<=n;r++) { for(int v1=0;v1<tot;v1++) for(int v2=0;v2<=v1;v2++) dp[l][r]=min(dp[l][r],ndp[r][v1][v2]+b*ca(hs[v1],hs[v2])+a); if(dp[l][r]>1000000000) continue; for(int v1=0;v1<tot;v1++) for(int v2=0;v2<=v1;v2++) { if(ndp[r][v1][v2]>1000000000) continue; ndp[r+1][max(v1,s[r+1])][min(v2,s[r+1])]=min(ndp[r+1][max(v1,s[r+1])][min(v2,s[r+1])],ndp[r][v1][v2]); for(int j=r+1;j<=n;j++) ndp[j][v1][v2]=min(ndp[j][v1][v2],ndp[r][v1][v2]+dp[r+1][j]); } } } printf("%d\n",dp[1][n]); return 0; }

## 参考 ##

没有

转载于:https://www.cnblogs.com/ranwen/p/9114945.html

[BZOJ]: https://www.lydsy.com/JudgeOnline/problem.php?id=4897