这道题启发我：一定要看清楚题目再开始编程，不论题目多么简单。
一道很简单的动态规划题目，难度根本不到2。
状态转移方程为：
d[i][j]=d[i][k]+d[k+1][j]+a[i]*a[k+1]*a[j+1]；
表示把从i到j的珠子合并获得的最大能量。
时间复杂度O(n^3)，100的数据规模很小了。
以下是我的代码：
#include<stdio.h>
#define max(a,b) (a>b?a:b)
long n,i,j,k,a[110],d[110][110]=
{0},s[330]={0},ans=0;
int main()
{
scanf("%ld",&n);
for(i=1;i<=n;i++)
scanf("%ld",&a[i]);
// Read In
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
d[i][j]=0;
for(i=1;i<=n*3;i++)
{
if(i<=n)
s[i]=i;
else if(i>n&&i<=2*n)
s[i]=i-n;
else s[i]=i-2*n;
}
ans=0;
// Init
for(k=1;k<=n-1;k++)// 间距
for(i=1;i<=n;i++)// 起点
for(j=i;j<=i+k-1;j++)// 中间点
{
d[s[i]][s[i+k]]=max(d[s[i]][s[j]]+d[s[j+1]][s[i+k]]+a[s[i]]*a[s[j+1]]*a[s[i+k+1]],d[s[i]][s[i+k]]);
ans=max(ans,d[s[i]][s[i+k]]);
}
// DP
printf("%ld\n",ans);
// Write
return 0;
}
posted on 2010-01-06 19:42
lee1r 阅读(241)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：动态规划