讨论 / 经典动规问题“堆石子”的升级版
沧海一声喵 2018-02-08 18:30:11
点我顶贴 收藏 删除
#include <cstdio>

#include <cstring>

using namespace std;

typedef struct node{

int qian,hou;

}node;

int main(){

int p,max=0,i,j,k,n,x,dp[201][201];node w[201];

scanf("%d",&n);

for(i=1;i<=n;i++){

scanf("%d",&x);

w[i-1].hou=w[i].qian=x;}

w[n].hou=w[1].qian;

for(i=1;i<=n;i++) w[i+n]=w[i];

for(p=1;p<=n;p++){

memset(dp,0,sizeof(dp));

for(i=p+n-2;i>=p;i--)

for(j=i+1;j<=p+n-1;j++)

for(k=i;k<j;k++)

if(dp[i][k]+dp[k+1][j]+w[i].qian*w[k].hou*w[j].hou>dp[i][j])

dp[i][j]=dp[i][k]+dp[k+1][j]+w[i].qian*w[k].hou*w[j].hou;

if(dp[p][p+n-1]>max) max=dp[p][p+n-1];}

printf("%d",max);

return 0;}

查看更多回复
提交回复