花店橱窗布置(dp)

题目大意:

n束花和m个花瓶(m>=n),一个花瓶最多放入一束花,每束花放入各个花瓶会产生对应的观赏值,要求n束花都必须按给出的顺序从左到右放入花瓶中,求能产生的最大观赏值和相应方案

思路过程:

1.先考虑求最大观赏值,用dp[i][j]来表示到第i个花瓶时放入第j束花能产生的最大观赏值,转移方程式为:

dp[i][j] = max(dp[i][j], dp[k][j-1] + a[j][i]);

2.然后是求对应方案,这里可以由后往前推,由最后一束花放入的位置推出最后第二束花放入的位置,再重复往前推算

易错点:

1.dp数组的初始化应全为最小负数
2.边界dp[1][1]的赋值容易遗漏

代码如下:

#include<bits/stdc++.h>
#include<algorithm>
typedef long long ll;
using namespace std;
#define N 105
#define M -0x3fffffff
ll a[N][N],q[N],id;
ll dp[N][N];
int main(void)
{
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			dp[i][j] = M;
		}
	}
	dp[1][1]=a[1][1];
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			//找前方最优的媒介点
			for(int k=1;k<i;k++)
				dp[i][j] = max(dp[i][j], dp[k][j-1] + a[j][i]);
		}
	}
	int x=m;
	for (int i = 1; i <= m; i++)
		if (dp[i][n] > dp[x][n])
			x = i;
	cout << dp[x][n] << endl;
	q[id++]=x;
	for (int i=x,j=n,k = x-1; k&&j>1; k--)
		if (dp[i][j] - a[j][i] == dp[k][j - 1]) {
			q[id++]=k;
			//向前推进
			i = k; j--; 
		}
	//翻转
    reverse(q, q + id);
	for (int i = 0; i < id; i++)
		cout << q[i] << "\n";
	return 0;
}