1≤N≤1001\leq N\leq 1001≤N≤100,0≤ai≤200\leq a_i\leq 200≤ai?≤20.
非常经典的一道例题...
从题面可以看出, 线性 DP 难以处理 (想了半天不知道怎么转移.... 所以只能用区间 DP, 这里可以看出, 最终的石子堆一定是由两个子堆合并而来, 即两个长度较小的区间的信息转移到了长度更长的区间, 划分点 k 是转移的决策(蓝书原话). 这个题用递归 + 记忆化搜索或者直接循环都能写, 我还是喜欢递归写法... 由分析可以写出转移方程: dp[l][r]=dp[l][i]+dp[i+1][r]+a[l...r], 其中 dp[l][r] 表示 l...r 合并而来的石子堆的最小花费 (最大花费同理).a[l...r] 可以通过前缀和 O(1)查询. 这里还有一个问题就是这是一个环形的圈, 对于环形的序列有一个很常用的处理方法就是复制一遍原序列并接在其后面, 这样只需要 1~n,2~n+1... 枚举一遍即可.
记得 dp[i][i]初始化为 0.
- #include <bits/stdc++.h>
- using namespace std;
- int n,a[205];
- int sum[205]={0};
- int dp1[205][205];// 最小
- int dp2[205][205];// 最大
- int process1(int l,int r)
- {
- if(dp1[l][r]!=0x3f3f3f3f)return dp1[l][r];
- int i;
- for(i=l;i<r;i++)
- {
- dp1[l][r]=min(dp1[l][r],process1(l,i)+process1(i+1,r)+sum[i]-sum[l]+a[l]+sum[r]-sum[i+1]+a[i+1]);
- }
- return dp1[l][r];
- }
- int process2(int l,int r)
- {
- if(dp2[l][r]!=0)return dp2[l][r];
- int i;
- for(i=l;i<r;i++)
- {
- dp2[l][r]=max(dp2[l][r],process2(l,i)+process2(i+1,r)+sum[i]-sum[l]+a[l]+sum[r]-sum[i+1]+a[i+1]);
- }
- return dp2[l][r];
- }
- int main()
- {
- cin>>n;
- int i;
- memset(dp1,0x3f3f3f3f,sizeof(dp1));
- memset(dp2,0,sizeof(dp2));
- for(i=1;i<=n;i++)
- {
- scanf("%d",&a[i]);
- a[n+i]=a[i];
- }
- for(i=1;i<=2*n;i++)
- {
- sum[i]=sum[i-1]+a[i];// 环形前缀和
- }
- for(i=1;i<=2*n;i++)
- {
- dp1[i][i]=0;// 初始化为 0 最开始的一小堆并非移动而得来
- dp2[i][i]=0;
- }
- int mmin=0x3f3f3f3f,mmax=0;
- for(i=1;i<=n;i++)// 枚举环形
- {
- mmin=min(mmin,process1(i,i+n-1));
- mmax=max(mmax,process2(i,i+n-1));
- }
- cout<<mmin<<endl<<mmax;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3465292.html