脚本宝典收集整理的这篇文章主要介绍了区间(环形)dp,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
1 #include <iostream> 2 3 using namespace std; 4 5 const int MAXN=110; 6 7 int n; 8 int a[MAXN*2]; 9 int dp[MAXN*2][MAXN*2]; 10 11 int main() 12 { 13 cin>>n; 14 for (int i=1;i<=n;i++) 15 { 16 cin>>a[i]; 17 a[i+n]=a[i]; 18 } 19 20 for (int len=2;len<=n;len++) //枚举合并长度 21 { 22 for (int i=1;i+len-1<=2*n;i++) //枚举左端点 23 { 24 int j=i+len-1; //右端点 25 for (int k=i;k<=j-1;k++) //枚举间断点 26 { 27 dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+a[i]*a[k+1]*a[j+1]); 28 } 29 } 30 } 31 32 int ans=0; 33 for (int i=1;i<=n;i++) 34 { 35 ans=max(ans,dp[i][i+n-1]); 36 } 37 cout<<ans<<endl; 38 39 return 0; 40 }
以上是脚本宝典为你收集整理的区间(环形)dp全部内容,希望文章能够帮你解决区间(环形)dp所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。