> #include <stdio.h>
> 
> #define MAXN 102
> #define MIN -9999999
> int f[MAXN][MAXN];
> int g[MAXN][MAXN];
> int a[MAXN][MAXN];
> int F,V;
> 
> int dp();
> 
> void display(int i,int j);
> 
> int main()
> {
> 	int i,j;
> 	scanf("%d%d",&F,&V);
> 	for (i = 1; i <= F; i++)
> 		for (j = 1; j <= V; j++)
> 			scanf("%d",&a[i][j]);
> 	i = dp();
> 	display(i,F);
> 	return 0;
> }
> 
> int dp()
> {
> 	int i,j,k;
> 	for (i = 0; i <= F; i++)
> 		for (j = 0; j <= V; j++)
> 			f[i][j] = MIN;
> 	f[0][0] = 0;
> 	for (i = 1; i <= F; i++)
> 		for (j = 1; j <= V; j++)
> 			for (k = 0; k < j; k++)
> 				if (f[i-1][k] > MIN)
> 					if (f[i-1][k] + a[i][j] > f[i][j])
> 					{
> 						f[i][j] = f[i-1][k] + a[i][j];
> 						g[i][j] = k;
> 					}
> 	k = MIN;j = -1;
> 	for (i = 0; i <= V; i++)
> 		if (f[F][i] > k)
> 		{
> 			k = f[F][i]; j = i;
> 		}
> 	printf("%d\n",k);
> 	return j;
> }
> 
> void display(int i,int j)
> {
> 	if (!j)
> 		return;
> 	display(g[j][i],j-1);
> 	printf("%d ",i);
> }
> 
> 
> 

• 多谢老板了! (0) LIANGLIANG 2004-06-13 12:37:03