学步园

其实吧。。多举几个例子，多画几个图。。就可以发现。。

第i号花的位置在第i-1号之后。。。（貌似题目里就说了哈。。。）

然后很easy的写出方程,opt[i][j] = max(opt[i-1][i-1....j-1]) + 美学值[i][j];

opt[i][j] 表示第i朵花放第j个位置的前i朵花的最大美学值

美学值[i][j]就是第i朵花放第j个位置的美学值。。

方程写出来了就好办了。。

然后还要记录路径。。那就再开个数组来记录噻

nex[i][j]表示opt[i][j]最优时，第i-1朵花的位置。。

然后给出不知道对不对的代码：。。。

（求测试数据）

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define MAX 101 
int n,m,p[MAX][MAX];
int road[MAX],opt[MAX][MAX],nex[MAX][MAX];
void init()
{
	scanf("%d %d",&m,&n);
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			scanf("%d",&p[i][j]);
		}
	}
}
int main()
{
	init();
	for (int i = 1; i <= m; i++)
	{
		for (int j = i; j <= n; j++)
		{
			int ans = 0,wh = 0;
			for (int k = i-1; k <= j-1; k++)
			{
				if ( ans < opt[i-1][k] )
				{
					ans = opt[i-1][k];
					wh = k;
				}
			}
			opt[i][j] = ans + p[i][j];//第i朵花放第j个地儿时。。。 
			nex[i][j] = wh;//目前最佳方案的 上一朵花放的地 
		}
	}
	int ans = 0,wh = 0;
	for (int i = m; i <= n; i++)
	{
		if ( ans < opt[m][i] )
		{
			ans = opt[m][i];
			wh = i;
		}
	}
	for (int i = m; i >= 1; i--)
	{
		road[i] = wh;
		wh = nex[i][wh];
	}
	cout<<ans<<endl;
	for (int i = 1; i <= m; i++)
	{
		cout<<road[i]<<' ';
	}
	return 0;
}