2019-12-26 xiaoh
题意
给定\(f\)盆花，\(v\)个花盆(\(1\leq f \leq v\leq100\))。第\(i\)朵花插在第\(j\)个花盆中都有一个美丽值\(A_{i,j}\)（\(A_{i,j}\) 可能为负数）。现在你要将所有花按照原有的顺序全部插进花盆中，求最大的美学值之和（保证答案在int范围内），并输出对应的方案（ACWing要求字典序最小，洛谷无特殊要求）
题解
先考虑如何求美学值。令\(f_{i,j}\) 为前i盆花摆进前j个盆子的最大美学值，则有以下几种情况：
1、第j个瓶子什么也不放，即\(f_{i,j}\) =max(\(f_{i,j-1}\),\(f_{i,j}\))
2、将花放进第j个盆子。那么遍历前面所有放过第i-1朵花的瓶子并取最大值，转移，即\(f_{i,j}\)=MAX{\(f_{i-1,k}\)+\(a_{i,j}\)}，k∈[i-1,j-1]。
我们令\(f_{0,x}\) =0,x∈[0,v],其余全为-inf即可计算最大值。接下来考虑如何输出方案。首先，我们可以将DP的过程理解为类似一个走方格的过程，我们只需在DP时记录每个节点是从哪个点转移过来的即可，然后每次从\(f_{n,m}\) 开始倒着搜到起点，然后一路找回来并输出即可。时间复杂度O（\(n^3\)），相当宽裕的复杂度，躺着都能过……
Code
#include<bits/stdc++.h>
#define inf 999999999
using namespace std;
inline int read()//快读
{
int ret=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return w*ret;
}
int n,m;
int a[110][110];//原数组
struct node{
int pos,num;
int p;
}f[110][110];//DP数组，其中p表示第i朵花插在第几个花瓶里，pos是转移位置
void find(int step,int x)//沿着记录下的转移位置一路找回去，并输出
{
if(step==0) return;
find(step-1,f[step][x].pos);
printf("%d ",x);
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) a[i][j]=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) f[i][j].num=-inf;//初始化
for(int i=1;i<=n;i++)
for(int j=i;j<=m;j++)
{
f[i][j].pos=f[i][j-1].pos;//第j个花瓶什么也不放
f[i][j].num=f[i][j-1].num;
f[i][j].p=f[i][j-1].p;
for(int k=i-1;k<j;k++)//遍历转移点并记录，ACW由于要求字典序最小，因此k要正序遍历
if(f[i-1][k].num+a[i][j]>f[i][j].num) f[i][j].num=f[i-1][k].num+a[i][j],f[i][j].pos=k,f[i][j].p=j;
}
printf("%d\n",f[n][m].num);
find(n,f[n][m].p);
printf("\n");
return 0;
}