#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);
}

• Re:大牛帮我看看吧~~ 官方数据都过了的... (1052) atlas_of_rruucc 2004-06-13 12:28:02
• hiahiahia…… 和我当时做的时候WA得一样 把display改成空函数就可以过了应该 (1052) atlas_of_rruucc 2004-06-13 12:29:18
  • 多谢老板了! (0) LIANGLIANG 2004-06-13 12:37:03
• 终于过了... 这个题目真是阴险... (1052) LIANGLIANG 2004-06-13 12:38:32
  • Re:终于过了... 这个题目真是阴险... (76) wincat 2007-08-06 01:47:51