题解 | #花店橱窗#

题目考点：二维线性DP （初学者可以参考代码对样例模拟状态转移的过程，有助于今后理解状态转移）

题目大意：n种花m个花瓶，花瓶顺序以及插入花的顺序固定，每种花在每个花瓶中美观度不同（有负数），问讲n种花插在哪n个花瓶里美观度最大。

题目分析：对于第i种花，它能获得的最大美观度为：在合法区间内，上一种花所在位置后面的花瓶中的最大美观度的位置（其中合法区间是指从上一种花(上一种花用k维护)放的位置开始，到使得i后面的话有花瓶可以放的区间，比如根据题目样例，对于第2种花来说，它最后能放的位置为4，后面至少留1个花瓶的位置）。
因此转移方程：dp [ i ][ j ] = max (dp [ i ][ j ], dp [ i-1 ][ k ] + v [ i ][ j ]);
代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 105, INF = 0x3f3f3f3f;
int dp[N][N], v[N][N], id[N];
int n, m;
int main()
{
  scanf("%d%d", &n, &m);

  for(int i = 1; i <= n; i++)
  for(int j = 1; j <= m; j++)    //dp数组初始化极小值
      scanf("%d", &v[i][j]) , dp[i][j] = -INF;

  for(int i = 1; i <= n; i++)
  for(int j = i; j <= m - (n-i); j++) //第i种花的合法区间(合法区间的定义写在上面了)
  for(int k = i-1; k < j; k++)        //k维护上一层的摆放情况
      dp[i][j] = max(dp[i][j], dp[i-1][k] + v[i][j]);

  //寻找最大美观度
  int ans = -INF;
  for(int i = 1; i <= m; i++)
      ans = max(ans, dp[n][i]);
  printf("%d\n", ans);

  //寻找位置  
  int pos = n;
  for(int i = n; i ; i--)  //倒推寻找位置
  for(int j = 1; j <= m; j++)  //对于每一种花，遍历所在层寻找
      if(dp[i][j] == ans) //ans对应dp维护的值，证明找到了位置
      {
          id[pos--] = j;   
          ans -= v[i][j];
          break;   //该层位置找到后记得直接跳到再上一层寻找上一层的位置
      }
  for(int i = 1; i <= n; i++)  //输出n种花的位置
      printf("%d ", id[i]);
  return 0;
}