不要说再见:问编程高手一道问题的算法

/*gcc编译通过*/
/*如果有多种选择能达到最优解，则这个程序对路径的选择是任意的*/
#include <stdio.h>
#include <mem.h>
#define MAXL 1000

int mark[MAXL],n;
int work[MAXL][2];
int ts[MAXL];

int main()
{
int i,j,res;
while(1)
{
/*输入的总旗子数量*/
scanf("%d",&n);

/*输入非正数则退出程序*/
if(n<=0) break;

/*依次输入各个旗子的分值*/
for(i=0;i<n;++i) scanf("%d",&mark[i]);

/*初始化*/
memset(ts,0,sizeof(ts));
memset(work,0,sizeof(work));
for(i=0;i<MAXL;++i) work[i][1]=-1;
res=0;

/*数组work[][0]记录的是：
如果一定要经过第i面旗子，则将一定经过第i面旗子所能达到的最优值记录在work[i][0]
work[][1]记录的是：
对于第i面旗子，达到最优值需要经过的前一面旗子的编号，如果该面旗是第1面旗，即前面没有满足条件的旗子，则将它记录为-1*/

/*动态规划核心部分*/
for(i=0;i<n;++i)
{
for(j=0;j<i;j++)
if( mark[i]>mark[j] && work[i][0]<=work[j][0] )
/*两个条件一个是j比i的分小，另一个相当于是找work[0][0]~work[i-1][0]中的最大值*/
{
work[i][0]=work[j][0];
work[i][1]=j;
}
work[i][0]+=mark[i];/*最优值找到，并将第i面旗子的分数加上*/

if(work[res][0]<work[i][0]) res=i;/*寻找所有旗子的最优值，即最终解*/
}
/*
如果一定要经过第i面旗子，求出它的最优值，方法是从前面的旗子中找到比第i面
旗子分值小的旗子（这样才满足这次绕过旗子的分数必须大于上次绕过旗子的分数
这个条件），并且在这些满足条件的旗子中选具有最大最优值的旗子作为它的前一
面旗*/

/*将通过旗子的顺序导出*/
i=res;
j=0;
while(i!=-1)
{
ts[j]=i;
i=work[ts[j]][1];
++j;
}

/*输出所能达到的最高分*/
printf("%d\n",work[res][0]);
/*输出依次应该通过第几面旗子，由于编号从0开始，这里自然对所有编号+1处理*/
printf("%d",ts[j-1]+1);
for(i=j-2;i>=0;--i) printf(" %d",ts[i]+1);
printf("\n");
}
return 0;
/*
样例输入：
7
1 10 2 9 3 8 4
样例输出：
14
1 3 5 6

这里还有学习动态规划的资料，希望能对你有所帮助
http://www.mydrs.org/program/list.asp?id=348
http://www.sdgh.net/bmzc/person/hwl/ao_sai/jsfd/dtgh3.htm
*/
}