讨论 / 递归求每一个阶段的最优解,从而求出整体最优解
360736293 2018-05-07 17:57:16
点我顶贴 收藏 删除
它其实就是一个“贪心思想”,意思就是,在处理数据的每一个阶段中,你找出每一个阶段的最优解,那么是不是在整体中,不同阶段最优解相加起来就是整体的最优解?

在看代码时,请一定要做到耐心,我的这个代码相对于别人已经做了很多的注释,读者看起来会轻松很多

如果还是不能理解,可以按照程序顺序往里面代值来观察每一段代码的作用

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

耐心 耐心 耐心 耐心 耐心 耐心 耐心 耐心 耐心

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

#include<stdio.h>

int main()

{

int max(int a,int b);

int N,i,j,k;

int dp[220][220]={0};

int a[220];

int ans;

scanf("%d",&N);

for(i=1; i<=N; i++){

scanf("%d",&a[i]);

a[N+i]=a[i]; //这里之后数组内容就是2,3,5,10,2,3,5,10 拉成了一条长链,以便下面的程序可以进行遍历处理

}

//--------------------------------------------------

for(j=1;j<N; j++)//分类处理球数(长度),就是不同的融球阶段,比如j等于1,就是最开始相邻的两个球开始融,j=2的话就是已经融过了一个球,完了再处理它跟下一个球融合,j=3就是融过两个球了依次类推

{

for(i=1; i+j<N*2; i++)//遍历在此阶段下,比较不同融球能量(它跟下面那个循环一同作用才能达到目的)

{

int tmp=0;

for(k=0; k<j; k++)//遍历不同融球顺序,找出最优(能量最大),在j=1的阶段时,这个比较融球顺序其实没必要,你看它出现了dp[1][1],就是0

{

tmp = max(tmp, dp[i][k+i] + dp[i+k+1][i+j] + a[i]*a[i+k+1]*a[i+j+1]);

}

dp[i][i+j] = tmp;

}

}

//--------------------------------------------------

ans = 0;

for(i=1; i<=N; i++){

ans = max(ans,dp[i][i+N-1]);

}

printf("%d",ans);

}

int max(int a,int b)

{

int temp;

temp=a;

if(temp<=b)

{

temp=b;

}

return temp;

}

#1 360736293@2018-05-07 18:01:14
回复 删除
说错了说错了,它没有用递归,是递推(顺序)
查看更多回复
提交回复