传送门

题意：

一个椭圆形操场环绕着有\(n\)堆石子，每堆石子有\(a_i\)个石头，相邻的两堆可以被合并，每次合并获得的权值是他们两堆石子的个数。现在问你能够获得的最大以及最小的权值和。

分析：

区间dp的经典题。

因为在区间dp的问题中，问题往往会跟某个区间\([l,r]\)的状态由关，因此我们往往会设置\(dp[l][r]\)为，区间\([l,r]\)被合并之后，能够获取的最大/最小的权值和。之后我们需要考虑对于状态\(dp[l][r]\)，它是由那些状态转移过来的。

显然，倘若需要区间\([l,r]\)被合并，那么这个大的区间肯定是由两个小区间进行合并而来的，我们不妨设一个变量\(k\)为大区间的分界点。那么当前的大区间\([l,r]\)，显然是由小区间\([l,k]\)以及小区间\([k+1,r]\)通过合并而来的。至此，我们就把一个大问题划分成了一个小的问题，故我们可以直接写出状态转移方程：\[dp[l,r]=\max(dp[l][r],dp[l][k]+dp[k+1][r]+val[l,r])\]

这里有一个技巧，在我们枚举所有区间的过程中，我们可以先枚举一个数\(p\)，代表枚举到的区间的长度，再枚举\(l=1,r=l+p\)，这样进行递推调用将会比较方便。

而对于这个问题，我们发现这个问题是可以在环上进行的，因此我们需要把原来的石头开成两倍，以满足环上合并的情况。

因为分别要枚举区间\([l,r]\)以及变量\(k\)，因此区间dp的总的时间复杂度为：\(\mathcal{O}(n^3)\)。

代码：

#include <bits/stdc++.h> #define maxn 205 using namespace std; int minn,maxx,dpmax[maxn][maxn],dpmin[maxn][maxn],a[301]; int sum[maxn]; const int inf=0x3f3f3f3f; int Sum(int l,int r){ return sum[r]-sum[l-1]; } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); a[i+n]=a[i]; } for(int i=n+1;i<=2*n;i++){ a[i+n]=a[i]; } for(int i=1;i<=2*n;i++){ sum[i]=sum[i-1]+a[i]; } for(int p=1;p<n;p++){ for(int i=1,j=i+p;(j<=2*n)&&(I<=2*n);i++,j=i+p){ dpmin[i][j]=inf; for(int k=i;k<j;k++){ dpmax[i][j]=max(dpmax[i][j],dpmax[i][k]+dpmax[k+1][j]+Sum(i,j)); dpmin[i][j]=min(dpmin[i][j],dpmin[i][k]+dpmin[k+1][j]+Sum(i,j)); } } } minn=inf; for(int i=1;i<=n;i++){ maxx=max(maxx,dpmax[i][i+n-1]); minn=min(minn,dpmin[i][i+n-1]); } printf("%d\n%d\n",minn,maxx); return 0; }

转载于:https://www.cnblogs.com/Chen-Jr/p/11212156.html

原文链接：https://blog.csdn.net/weixin_30342827/article/details/99145479

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。