這道題啟發我：一定要看清楚題目再開始編程，不論題目多么簡單。
一道很簡單的動態規劃題目，難度根本不到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 閱讀(259)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態規劃