讨论 / 能量项链麻烦找下错只得了50分
liaoyu 2017-02-07 20:52:49
点我顶贴 收藏 删除
#include<iostream>

#include<cstdio>

using namespace std;

int n;

int a[6000];

long long dp[600][600];

struct ss

{int tou,wei;

}data[6000];

int main()

{

cin>>n;

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

cin>>a[i];

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

{

data[i].tou=a[i];

data[i].wei=a[i+1];

}

data[n].tou=a[n];

data[n].wei=a[1];

data[0].tou=data[n].tou;

data[0].wei=data[n].wei;

data[n+1].tou=data[1].tou;

data[n+1].wei=data[1].wei;

for(int i=n;i>=0;i--)

for(int j=i+1;j<=n+1;j++)

{

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

dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+data[i].tou*data[k].wei*data[j].wei);

}

cout<<max(dp[0][n-1],max(dp[2][n+1],dp[1][n]));

return 0;

}

#1 owen2008@2019-03-10 20:23:19
回复 删除
你看看我的(AC):

#include<bits/stdc++.h>

using namespace std;

int f[405][405];

int n,a[205];

int main()

{

cin >> n;

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

{

cin >> a[i];

a[n+i]=a[i];

}

for(int i=2;i<=n+1;i++)

{

for(int l=1;l+i-1<=2*n;l++)

{

int r=l+i-1;

for(int k=l+1;k<=l+i-2;k++)

f[l][r]=max(f[l][r],f[l][k]+f[k][r]+a[l]*a[k]*a[r]);

}

}

int res=0;

for (int i=1;i<=n;i++) res=max(res,f[i][n+i]);

cout << res;

return 0;

}

查看更多回复
提交回复