#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
int N=0;
int mark[300];
bool vis[300][300];
long long d[300][300];
long long max(long long &a,long long &b)
{
if(a>b) return a;
else return b;
}
void init()
{
for(int i=0;i!=300;++i)
for(int j=0;j!=300;++j) vis[i][j]=d[i][j]=0;
}

long long dp(int i,int j)
{
if(i==j) return 0;
if(vis[i][j]) return d[i][j];
for(int k=i;k<j;++k) d[i][j]=max(d[i][j],dp(i,k)+dp(k+1,j)+mark[i]*mark[k+1]*mark[j+1]);
vis[i][j]=1;
return d[i][j];
}
int main()
{
long long ans=0;
scanf("%d",&N);
for(int i=1;i<=N;++i)
{
scanf("%d",mark+i);
mark[i+N]=mark[i];
}
mark[N+N+1]=mark[1];
for(int i=1;i<=N;++i)
{
init();
ans=max(ans,dp(i,i+N-1));
}
cout<<ans<<endl;
return 0;
}

代码很丑陋，效率还可以...

#include<cstdio>
#include<cstring>
using namespace std;
inline int read() {
int f=1,x=0; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return f*x;
}
const int N=105;
int a[N<<1],n,ans,dp[N<<1][N<<1];

inline int max(int a,int b) {return a>b?a:b;}
inline int cal(int l,int k,int r) {
return dp[l][k-1]+dp[k][r]+a[l]*a[k]*a[r+1];
}
int main() {
n=read();
for(int i=1;i<=n;++i)
a[i]=a[i+n]=read();
for(int len=1;len<n;++len)
for(int l=1;l<=n;++l) {
int r=l+len;
dp[l][r]=dp[l][r-1]+a[l]*a[r]*a[r+1];
for(int k=1;k<len;++k)
dp[l][r]=max(dp[l][r],cal(l,l+k,r));
if(r<=n) dp[l+n][r+n]=dp[l][r];
}
for(int i=1;i<=n;++i)
ans=max(ans,dp[i][i+n-1]);
printf("%d\n",ans);
return 0;
}

http://www.cnblogs.com/oierforever/p/4764077.html

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int a[200 + 2];
int f[200 + 2][200 + 2];
int n;

inline int max( int a , int b )
{
if( a > b )
return a;
return b;
}

int dp( int l , int r )
{
if( l == r )
return 0;
if( f[l][r] != -1 )
return f[l][r];
int i;
for( i = l ; i < r ; i++ )
f[l][r] = max( f[l][r] , dp( l , i ) + dp( i + 1 , r ) + a[l] * a[i + 1] * a[r + 1] );
return f[l][r];
}

int ans;
int i;

int main()
{
scanf( "%d" , &n );
for( i = 1 ; i <= n ; i++ )
scanf( "%d" , &a[i] );
for( i = 1 ; i <= n ; i++ )
a[i + n] = a[i];
memset( f , -1 , sizeof( f ) );
for( i = 1 ; i <= n ; i++ )
ans = max( ans , dp( i , i + n - 1 ) );
cout << ans << endl;
return 0;
}

Inline Code

• foo bar ### Block Code #include<iostream> using namespace std; int main() { int i,j,k,l,n,a; int energy[202]/每个珠子所带的能量*/,x[202][202]={}/*状态转移方程，从i到j合成的最大能量*/; a=0;//初始化，比大 cin>>n; for(i=1;i<=n;i++) { cin>>energy[i]; energy[n+i]=energy[i];//因为环成一圈，所以先设成两圈 } for(l=1;l<=n;l++)//先循环长度 { for(i=1;i<=2*n;i++)//再循环起点 { j=i+l;//终点=起点+长度 if(j<=2*n)//如果没有越界 { for(k=i+1;k<=j-1;k++)//就在这段中寻找断点 { x[i][j]=max(x[i][k]+x[k][j]+energy[i]*energy[k]*energy[j]/*在这里断开所吸收的能量*/,x[i][j]/*之前的断点所吸收的最大值*/); } } } } for(i=1;i<=n;i++) { if(x[i][i+n]>a) { a=x[i][i+n];//找最大咯 } } cout<<a<<endl;//输出答案咯 //system ("pause"); return 0; }

#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,w[301],f[301][301]={},ans=-1;
int main(){

int i,j,k,t;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&w[i]);
w[n+i]=w[i];
}
for(j=1;j<=2*n-1;j++){
for(i=j;i>=max(1,j-n+1);i--){
if(i==j) f[i][j]=0;
for(k=i;k<j;k++){
t=w[i]*w[k+1]*w[j+1];
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+t);
}
}
if(j>=n) ans=max(ans,f[j-n+1][j]);
}

printf("%d",ans);
return 0;
}

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

-------------------------

Accepted 有效得分：100 有效耗时：0ms

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{ ** int N,i,j,k,a[2][101]={0},b[2][101]={0},sum=0,max=0;**
cin >> N;
1.for(i=1;i<=N;i++)
cin >> a[0][i];
for(i=1;i<N;i++)
a[1][i]=a[0][i+1];
a[1][N]=a[0][1];
2.for(i=1;i<=N;i++)
{ b[0][i]=a[0][i];
b[1][i]=a[1][i];
}

*for(k=1;k<=N;k++)
{ sum=0; i=k;
for(i=1;i<=N;i++)
{ b[0][i]=a[0][i];
b[1][i]=a[1][i];
}
do
{ if(i>N) i=1;
if(i==N) j=1;
else j=i+1;
sum=sum+b[0][i]*b[0][j]*b[1][j];
b[0][j]=b[0][i]; i++;
cout << k << " " << b[0][j] << " " << b[1][j] << endl;
}while(i!=k);
if(sum > max)max=sum;
* }
cout << max << endl;
return 0;
* }

#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,w[301],f[301][301]={},ans=-1;
int main(){
int i,j,k,t;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&w[i]);
w[n+i]=w[i];
}
for(j=1;j<=2*n-1;j++){
for(i=j;i>=max(1,j-n+1);i--){
if(i==j) f[i][j]=0;
for(k=i;k<j;k++){
t=w[i]*w[k+1]*w[j+1];
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+t);
}
}
if(j>=n) ans=max(ans,f[j-n+1][j]);
}

printf("%d",ans);
return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
int n,v[201];
long long ans=0,f[201][201];
int main(){
cin>>n;
for(int i=0;i<n;i++)cin>>v[i],v[i+n]=v[i];
for(int i=0;i<2*n;i++)fill(f[i],f[i]+2*n,0);
for(int j=2;j<2*n;j++)
for(int i=j-2;i>=j-n&&i>=0;i--)
for(int k=i+1;k<j;k++)
f[i][j]=max(f[i][j],f[i][k]+f[k][j]+v[i]*v[k]*v[j]),
ans=max(f[i][j],ans);
cout<<ans;
return 0;
}

#include<cstdio>
#include<algorithm>
int n,ans=0,t[210],w[210],a[210][210];
int get(int l,int r) {
if (a[l][r]) return a[l][r];
for (int i=l; i<r; i++) a[l][r]=std::max(a[l][r],get(l,i)+get(i+1,r)+t[l]*w[i]*w[r]);
return a[l][r];
}
int main() {
scanf("%d",&n);
for (int i=1; i<=n; i++) {
scanf("%d",&t[i]);
w[i-1]=t[i+n]=w[i+n-1]=t[i];
}
for (int i=1; i<=n; i++) ans=std::max(ans,get(i,i+n-1));
printf("%d",ans);
}

Program eee;
Uses math;
Var a:array[1..2000]of longint;
f:array[1..2000,1..2000]of longint;
m,n,i,j,k:longint;
Begin
readln(n);
for i:=1to n do
begin read(a[i]);a[i+n]:=a[i];end;

for i:=1to n do f[i,i]:=0; //以上为初始化，把环换成线。

for i:=2*n-3 downto 1 do
for j:=i+2 to i+n do
for k:=i+1 to j-1 do
f[i,j]:=max(f[i,j],f[i,k]+f[k,j]+a[i]*a[k]*a[j]); //(i和j即为两个即将合并的珠子的左端点和右端点）求i和j 的最大值时，枚举i和j之间的数K(就是两个珠子的公共部分）

m:=0;
for i:=1to n do
m:=max(f[i,i+n],m); //有n个起点，所以找最大的那个
writeln(m);
end.

//谁比我短？～～

#include<cstdio>
int d[250][110],a[250],n,ans;
int Max(int a,int b){return a>b?a:b;}
int main()
{scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
for(int i=n;i<=2*n-1;i++)a[i]=a[i-n];
for(int i=3;i<=n+1;i++)
for(int j=i-1;j<=2*n-1;j++)
for(int k=j-i+2;k<j;k++)

d[j][i]=Max(d[k][k-j+i]+d[j][j-k+1]+a[j-i+1]*a[k]*a[j],d[j][i]);

ans=0;
for(int i=n;i<=2*n-1;i++)ans=Max(ans,d[i][n+1]);
printf("%d\n",ans);
}

var
n,i,j:longint;
f:array[1..200,1..200]of longint;
a:array[1..200]of longint;
procedure init;
begin
readln(n);
for i:=1 to n do
begin
read(a[i]);
a[i+n]:=a[i];
end;
fillchar(f,sizeof(f),$ff);
end;

procedure dp(i,j:longint);
var s,k:longint;
begin
if f[i,j]<>-1 then exit;
if (i<n)and(j<n) then
begin
dp(i+n,j+n);
f[i,j]:=f[i+n,j+n];
end;
if i=j then
begin
f[i,j]:=0;
exit;
end;
s:=a[i]*a[j mod n+1];
if i+1=j then
begin
f[i,j]:=s*a[j];
exit;
end;
for k:=i to j-1 do
begin
dp(i,k);
dp(k+1,j);
if f[i,k]+f[k+1,j]+s*a[k+1]>f[i,j] then
f[i,j]:=f[i,k]+f[k+1,j]+s*a[k+1];
end;
end;

procedure main;
var ans:longint;
begin
for i:=1 to n do
for j:=i to i+n-1 do
dp(i,j);
ans:=-1;
for i:=1 to n do
if f[i,i+n-1]>ans then ans:=f[i,i+n-1];
writeln(ans);
end;

begin
init;
main;
end.

区间动规，枚举断点位置，嗯

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

23行神短代码，秒掉不解释……

#include

#include

#include

using namespace std;

int n,th[210][2],ans,f[210][210];

int main(){

scanf("%d",&n);

for(int i=1;i

这题不开两倍也可以过

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

typedef long long LL;

int n;

const int MAXN = 200;

LL dd[MAXN][2];

LL Mul[MAXN][MAXN];

LL sMax[MAXN][MAXN];

int main(){

//freopen("d:/2.in","r",stdin);

LL t;

LL maxl;

scanf("%d",&n);

{

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

{

scanf("%lld",&t);

dd[i][0] = t;

dd[(n+i-1)%n][1] = t;

}

memset(sMax,0,sizeof(sMax));

for (int i = 2; i

var f:array[1..300,1..300]of longint;

a:array[1..300]of integer;

n,i,j,k:integer;

max,ans:longint;

begin

readln(n);

for i:=1 to n do read(a[i]);

for i:=n+1 to 2*n do begin

a[i]:=a;

end;

fillchar(f,sizeof(f),0);

for i:=1 to n do f:=a[i]*a*a;

for i:=2*n-1 downto 1 do

for j:=i+1 to i+n-1 do

begin

max:=0;

for k:=i to j-1 do

if f+f[k+1,j]+a[i]*a[k+1]*a[j+1]>max

then max:=f+f[k+1,j]+a[i]*a[k+1]*a[j+1];

f:=max;

end;

ans:=0;

for i:=1 to n do

if f>ans then ans:=f;

writeln(ans);

end.

begin

{初值}

for j:=2 to n do

for i:=1 to n*2-j do begin

for k:=1 to j-1 do

if f+f+a[i]*a*a>f then

f:=f+f+a[i]*a*a;｛动归｝

end;

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

矩阵连乘积问题

只不过是环状

AC！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms