信息学奥赛一本通T1279-橱窗布置

解题思路:

注意事项:

参考代码:

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e2 + 10;
int a[N][N],f,v,dp[N][N],b[N][N],res[N];
int main()
{	
	cin >> f >> v;
	for(int i = 1; i <= f; i ++)
		for(int j = 1; j <= v; j ++)
			cin >> a[i][j];
	memset(dp, 0xc0, sizeof dp);
	for(int i = 0; i <= v; i ++) dp[0][i] = 0;
	for(int i = 1; i <= f; i ++)
		for(int j = 1; j <= v; j ++)
			{
				if(dp[i][j-1] < dp[i-1][j-1] + a[i][j] ){
					dp[i][j] = dp[i-1][j-1] + a[i][j];
					b[i][j] = j;
				}
				else{
					dp[i][j] = dp[i][j-1];
					b[i][j] = b[i][j-1];
				}
			}
	cout << dp[f][v] << endl;
	int x = f, y = v, i = 0;
	while(x > 0){
		res[i ++] = b[x][v];
		v = b[x][v]-1;
		x -= 1;
	}
	for(int j = i - 1; j >= 0; j --)
		cout << res[j] << ' ';
	return 0;
}