CH5E02 花店橱窗【线性DP】
5E02 花店橱窗 0x5E「动态规划」练习
背景
xq和他的老婆xz最近开了一家花店,他们准备把店里最好看的花都摆在橱窗里。但是他们有很多花瓶,每个花瓶都具有各自的特点,因此,当各个花瓶中放入不同的花束时,会产生不同的美学效果。为了使橱窗里的花摆放的最合适,他们得想个办法安排每种花的摆放位置。
可是因为xq和xz每天都太忙,没有时间设计橱窗里花的摆法,所以他们想让你帮他们求出花摆放的最大美观程度和每种花所放的位置。
描述
每种花都有一个标识,假设杜鹃花的标识数为1,秋海棠的标识数为2,康乃馨的标识数为3,所有的花束在放入花瓶时必须保持其标识数的顺序,即:杜鹃花必须放在秋海棠左边的花瓶中,秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目。则多余的花瓶必须空置,且每个花瓶中只能放一束花。
每种花放在不同的瓶子里会产生不同的美观程度,美观程度可能是正数也可能是负数。
上述例子中,花瓶与花束的不同搭配所具有的美观程度,如下表所示:
花 瓶
1 2 3 4 5
1 (杜鹃花) 7 23 -5 -24 16
2 (秋海棠) 5 21 -4 10 23
3 (康乃馨) -21 5 -4 -20 20
根据上表,杜鹃花放在花瓶2中,会显得非常好看;但若放在花瓶4中则显得十分难看。
为取得最大美观程度,你必须在保持花束顺序的前提下,使花束的摆放取得最大的美学值,并求出每种花应该摆放的花瓶的编号。
输入格式
第1行:两个整数F和V,表示xq和xz一共有F种花,V个花瓶。(1<=F<=V<=100)
第2行到第F+1行:每行有V个数,表示花摆放在不同花瓶里的美观程度值value。(美观程度和不超过maxint,美观程度有正有负)
输出格式
输出有两行:第一行为输出最大美观程度和的值,第二行有F个数表示每朵花应该摆放的花瓶的编号。若有多种方案,输出字典序较小的(美观程度不变的情况下,花尽量往前放)
样例输入
3 5
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20
样例输出
53
2 4 5
题意:
有f种花,v个花瓶。每种花放在不同的花瓶得到的beauty值是不同的,给出这个价值矩阵。摆放花的顺序不可以改变,即花的序号是递增的。现在问一个方案,使得beauty之和是最大的。输出方案。
思路:
原来的思路是 用dp[i][j]表示前j个花瓶摆了i种花,用j作为阶段。但是这样好像不是很好输出路径。
应该用dp[i][j]表示第i种花放在第j个花瓶。然后枚举k,表示第i-1种花放在第k个花瓶。
//#include <bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<stdio.h>
#include<cstring>
#include<vector>
#include<map> #define inf 0x3f3f3f3f
using namespace std;
typedef long long LL; int f, v;
int val[][], dp[][], path[][], res[]; int main()
{
scanf("%d%d", &f, &v);
for(int i = ; i <= f; i++){
for(int j = ; j <= v; j++){
scanf("%d", &val[i][j]);
}
} memset(dp, -inf, sizeof(dp));
for(int i = ; i <= v; i++){
dp[][i] = val[][i];
}
for(int i = ; i <= f; i++){
for(int j = i; j <= v - (f - i); j++){
for(int k = i - ; k < j; k++){
if(dp[i - ][k] > dp[i][j]){
dp[i][j] = dp[i - ][k];
path[i][j] = k;
}
}
dp[i][j] += val[i][j];
}
} int pos, ans = -inf;
for(int i = v - f; i <= v; i++){
if(dp[f][i] > ans){
ans = dp[f][i];
pos = i;
}
}
printf("%d\n", ans);
res[f] = pos;
for(int i = f - ; i >= ; i--){
res[i] = path[i + ][res[i + ]];
}
printf("%d", res[]);
for(int i = ; i <= f; i++){
printf(" %d", res[i]);
}
printf("\n");
return ;
}
最新文章
- 学习Spring——依赖注入
- ES6之字符串扩展方法(常用)
- 开窗函数 First_Value 和 Last_Value
- Linux账户密码过期安全策略设置
- 运行时报错-Verify the Developer App certificate for youraccount is trusted on your device. Open Settings on Mayoyi_sakura and navigate to General ->; Device Management, then select your
- Xcode的版本功能特点简要回顾
- css制作简单的导航栏
- 九度OJ1084
- 网络复习之TCP
- C++ hello world
- html表格合并(行,一排)
- Candy 解答
- 摘抄来自论坛的一些DDD讨论
- FFmpeg安装(windows环境)
- ssm简单搭建
- zabbix监控到异常后自动执行对应命令
- JS 代码中到底加不加分号
- push的时候报错:Permission denied (publickey)
- MySQL数据类型2
- JUnit Parametrized Tests