因为学习区间 dp 之前我会 floyd, 所以并不难掌握
dp[i][j]=max/min(dp[i][j],dp[i][k]+dp[k][j])
石子合并: https://www.luogu.org/problemnew/show/P1880
- #include <bits/stdc++.h>
- #define inf 1e7
- #define lll long long int
- #define void inline void
- using namespace std;
- int n,end,dp[500][500],a[1000],sum[1000],dp1[500][500],minn=912333,maxx=-1;
- int main(){
- iOS::sync_with_stdio(0);
- memset(dp,-999999,sizeof(dp));
- memset(dp1,9999999,sizeof(dp1));// 求最大值和最小值时应记得赋初值
- cin>>n;
- for(int i=1;i<=n;i++)
- {
- cin>>a[i];
- sum[i]=sum[i-1]+a[i];
- dp[i][i]=0; // 这里是在设置边界 后面 k 是可以 = i 的
- dp1[i][i]=0;
- }
- for(int i=1;i<=n;i++)
- {
- sum[i+n]=sum[i+n-1]+a[i];
- dp[i+n][i+n]=0;
- dp1[i+n][i+n]=0;// 这里是在设置边界 后面 k 是可以 = i 的
- }
- for(int i=1;i<=n;i++){
- for(int j=1;j+i<=n*2;j++){// 关于为什么是 2*n, 其实这是一个环, 我们需要破环成链
- end=i+j;
- for(int k=j;k<end;k++){
- dp[j][end]=max(dp[j][end],dp[j][k]+dp[k+1][end]+sum[end]-sum[j-1]);
- dp1[j][end]=min(dp1[j][end],dp1[j][k]+dp1[k+1][end]+sum[end]-sum[j-1]);//dp 转移方程
- }
- }
- }
- for(int i=1;i<=n;i++){
minn=min(minn,dp1[i][i+n-1]); 但最后还是 n 的长度, 我们可以理解成为 n 条链的最大值 / 最小值
- maxx=max(maxx,dp[i][i+n-1]);
- }
- cout<<minn<<endl<<maxx;
- return 0;
- }
区间 dp 要想学好, 建议学习 floyd
来源: http://www.bubuko.com/infodetail-2982274.html