https://www.luogu.org/problemnew/show/P1880
解题过程:本次的题目把石子围成一个环,与排成一列的版本有些不一样,可以在后面数组后面再接上n个元素,表示连续n个石子表示首尾相接,取最大值和最小值。
比如有4堆
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
第二种情况是创造4和1先合并的条件
第三种情况是创造4和1先合并再合并2的条件
第四种情况是创造4和1合并后的新堆 再与 2和3合并后的新堆 合并的条件
#include<stdio.h> #include<iostream> #include<algorithm> #include<cstring> #include<math.h> #include<string> #define ll long long #define inf 0x3f3f3f3f using namespace std; int a[305]; int sum[305][305]; int dp1[305][305]; int dp2[305][305]; int n,maxx,minn; int main() { scanf("%d",&n); memset(sum,0,sizeof(sum)); memset(dp1,inf,sizeof(dp1)); memset(dp2,0,sizeof(dp2)); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); a[i+n]=a[i]; sum[i][i]=a[i]; sum[i+n][i+n]=a[i]; dp1[i][i]=dp1[i+n][i+n]=0; dp2[i][i]=dp2[i+n][i+n]=0; } for(int len=2;len<=n;len++)///长度只能到n { for(int i=1;i+len-1<=2*n;i++)///i是起点 { int j=i+len-1; ///j是终点 sum[i][j]=sum[i][j-1]+sum[j][j]; for(int k=i+1;k<=j;k++)///以k-1为分界点 { dp1[i][j]=min(dp1[i][j], dp1[i][k-1]+dp1[k][j]+sum[i][j] ); dp2[i][j]=max(dp2[i][j], dp2[i][k-1]+dp2[k][j]+sum[i][j] ); } } } minn=inf; maxx=-1; for(int i=1;i<=n;i++)///寻找区间长度为n的最值 { minn=min(dp1[i][i+n-1],minn); maxx=max(dp2[i][i+n-1],maxx); } printf("%d\n%d\n",minn,maxx); return 0; }View Code