心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0

这道题启发我:一定要看清楚题目再开始编程,不论题目多么简单。

一道很简单的动态规划题目,难度根本不到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 阅读(249) 评论(0)  编辑 收藏 引用 所属分类: 题目分类:动态规划

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理