[Contents]
- 无环，朴素算法，\(O(n^3)\)
- 有环，朴素算法，\(O(n^3)\)
GrsiaWachs、四边形不等式优化
无环，朴素算法，\(O(n^3)\)
用\(f[i][j]\)表示\(i\sim j\)的最小得分，枚举长度\(len=2\sim n\)，对于每个长度，枚举左端点\(l\)，算出右端点\(r\)，然后再枚举从分割位置\(k=l\sim r-1\)，注意需要前缀和维护一下区间和。
\(f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+a[r]-a[l-1])\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,a[310],dp[310][310];
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1];
for(int len=2;len<=n;len++){
for(int l=1;l+len-1<=n;l++){
int r=l+len-1;
dp[l][r]=INT_MAX;
for(int k=l;k<r;k++){
dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+a[r]-a[l-1]);
}
}
}
cout<<dp[1][n];
return 0;
}
有环，朴素算法，\(O(n^3)\)
把\(a\)重复一次接到末尾，长度就是\(2n\)，此时可以转化为无环的做法。\(len\)还是\(2\sim n\)，但是\((l,r)\)区间最多可以延伸到\(2n\)。最终求出\(max(f[1][n],f[2][n+1],f[3][n+2],…,f[n-1][2n])\)即可，\(min\)同理。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,a[210];
int dp[210][210],dp2[210][210];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
a[n+i]=a[i];
}
for(int i=1;i<=2*n;i++) a[i]+=a[i-1];
for(int len=2;len<=n;len++){
for(int l=1;l+len-1<=2*n;l++){
int r=l+len-1;
dp[l][r]=INT_MIN;
dp2[l][r]=INT_MAX;
for(int k=l;k<r;k++){
dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]+a[r]-a[l-1]);
dp2[l][r]=min(dp2[l][r],dp2[l][k]+dp2[k+1][r]+a[r]-a[l-1]);
}
}
}
int maxx=INT_MIN,minn=INT_MAX;
for(int i=1;i<=n;i++){
maxx=max(maxx,dp[i][i+n-1]);
minn=min(minn,dp2[i][i+n-1]);
}
cout<<minn<<endl<<maxx;
return 0;
}