题目大意:
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;
}