题解 P1854 【[IOI1999]花店橱窗布置】
Drinkkk
·
·
题解
【标签】
DP50题，详见https://www.luogu.org/blog/cccx2016/dp50-ti-ti-hao。
【题目描述】
某花店现有F束花，每一束花的品种都不一样，同时至少有同样数量的花瓶，被按顺序摆成一行，花瓶的位置是固定的，从左到右按1到V顺序编号，V是花瓶的数目。花束可以移动，并且每束花用1到F的整数标识。如果I<J，则花束I必须放在花束J左边的花瓶中。例如，假设杜鹃花的标识数为1，秋海棠的标识数为2，康乃馨的标识数为3，所有花束在放入花瓶时必须保持其标识数的顺序，即杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目，则多余的花瓶必须空，即每个花瓶只能放一束花。
每个花瓶的形状和颜色也不相同，因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以美学值（一个整数）来表示，空置花瓶的美学值为0。在上述的例子中，花瓶与花束的不同搭配所具有的美学值，可以用如下的表格来表示：
| 花名/花瓶编号 |
花瓶1 |
花瓶2 |
花瓶3 |
花瓶4 |
花瓶5 |
| 杜鹃花 |
7 |
23 |
-5 |
-24 |
16 |
| 秋海棠 |
5 |
21 |
-4 |
10 |
23 |
| 康乃馨 |
-21 |
5 |
-4 |
-20 |
20 |
根据表格，我们可以发现：杜鹃花放在花瓶2中，会显得非常好看，但若放在花瓶4中，则显得很难看。
为了取得最佳的美学效果，必须在保持花束顺序的前提下，使花的摆放取得最大的美学值，如果具有最大美学值的摆放方式不止一种，则输出任何一种方案即可。
【输入输出格式】
-
输入格式
输入文件的第一行是两个整数F和V，分别为花束数和花瓶数（1 \leq F≤100,F \leq V \leq 100）。接下来是矩阵A_{i,j},它有I行，每行J个整数，A_{i,j}表示花束I摆放在花瓶J中的美学值。
-
输出格式
输出文件的第一行是一个整数，为最大的美学值；接下来有F行，每行两个数，为那束花放入那个花瓶的编号。
【输入输出样例】
我们考虑进行深度优先搜索（DFS），对每一束花的位置进行枚举。在更新最优解的过程中更新摆放方案。但是这样很显然会超时。
$100$分思路：
我们考虑动态规划（即DP）。一开始我很天真的想，我们可不可以用$f[i][j]$来表示前$i$个花瓶中插$j$朵花的最优解（即$C_j^i$的最优解）。然后用一个二重循环来枚举$i$和$j$。然后发现$f[i][]$可以从$f[i-1][]$中转移过来。其实还有另一种方法来表示我们的$f$数组。我们考虑用$f[i][j]$来表示第$i$束花插在第$j$个花瓶里时的最优解（即最大的美学值）。那么动态转移方程就是$f[i][j]=max(f[i-1][i-1],f[i-1][i]......f[i-1][j-1])+a[i][j]$。那么答案就在$f[n][n]$和$f[n][m]$之间，因为第$n$束花在最靠前的情况下只能够放在第$n$个花瓶里。一定要注意这点，不然会WA哦。
感谢@creed_ 的帮助！
$10$分代码：
```cpp
#include <cstdio>
int n=0,m=0;
int sc[101][101];
int ans[101],a[101];
int da=0;
int max(int x,int y)
{
return x>y?x:y;
}
void dfs(int x,int su)
{
if(x==n+1)
{
if(su>da)
{
da=su;
for(int i=1;i<=n;i++)
{
ans[i]=a[i];
}
}
return ;
}
for(int i=a[x-1]+1;i<=m;i++)
{
a[x]=i;
dfs(x+1,su+sc[x][i]);
a[x]=0;
}
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&sc[i][j]);
}
}
dfs(1,0);
printf("%d\n",da);
for(int i=1;i<=n;i++)
{
printf("%d ",ans[i]);
}
return 0;
}
```
$100$分（满分）代码$1$：
```
#include <cstdio>
int f[101][101],a[101][101];
int inf=999999999;
int min(int x,int y)
{
return x<y?x:y;
}
int max(int x,int y)
{
return x>y?x:y;
}
void print(int x,int y)
{
if(x>0)
{
int n=x;
while(f[n][x]!=y)
{
n++;
}
print(x-1,y-a[x][n]);
printf("%d ",n);
}
}
int main()
{
int n=0,m=0;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
f[j][i]=-inf;
}
}
for(int i=1;i<=m;i++)
{
f[0][i]=-inf;
}
f[0][0]=0;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=min(n,i);j++)
{
f[i][j]=max(f[i-1][j],f[i-1][j-1]+a[j][i]);
}
}
printf("%d\n",f[m][n]);
print(n,f[m][n]);
return 0;
}
```
$100$分代码$2$：
```
#include <cstdio>
int f[101][101],a[101][101];
int max(int x,int y)
{
return x>y?x:y;
}
void print(int x,int y)
{
if(x>0)
{
int n=x;
while(f[x][n]!=y)
{
n++;
}
print(x-1,y-a[x][n]);
printf("%d ",n);
}
}
int main()
{
int n=0,m=0;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
f[i][j]=-2147483647;
}
}
for(int i=1;i<=n;i++)
{
for(int j=i;j<=m;j++)
{
for(int k=i-1;k<=j-1;k++)
{
f[i][j]=max(f[i][j],f[i-1][k]+a[i][j]);
}
}
}
int ans=0;
for(int i=n;i<=m;i++)
{
ans=max(ans,f[n][i]);
}
printf("%d\n",ans);
print(n,ans);
return 0;
}
```