专题网站开发报价,怎么seo快速排名,网页版传奇制作教程,php做电子商务网站的种类花店橱窗 https://ac.nowcoder.com/acm/contest/24213/1005 题目描述
小q和他的老婆小z最近开了一家花店#xff0c;他们准备把店里最好看的花都摆在橱窗里。 但是他们有很多花瓶#xff0c;每个花瓶都具有各自的特点#xff0c;因此#xff0c;当各个花瓶中放入不同…花店橱窗 https://ac.nowcoder.com/acm/contest/24213/1005 题目描述
小q和他的老婆小z最近开了一家花店他们准备把店里最好看的花都摆在橱窗里。 但是他们有很多花瓶每个花瓶都具有各自的特点因此当各个花瓶中放入不同的花束时会产生不同的美学效果。 为了使橱窗里的花摆放的最合适他们得想个办法安排每种花的摆放位置。 可是因为小q和小z每天都太忙没有时间设计橱窗里花的摆法所以他们想让你帮他们求出花摆放的最大美观程度和每种花所放的位置。 每种花都有一个标识假设杜鹃花的标识数为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表示共有F种花V个花瓶。第2行到第F1行每行有V个数表示花摆放在不同花瓶里的美观程度值value。(美观程度和小于2312^{31}231美观程度有正有负) 输出描述 输出有两行第一行为输出最大美观程度和的值第二行有F个数表示每朵花应该摆放的花瓶的编号。若有多种方案输出字典序较小的方案美观程度不变的情况下花尽量往前放。 样例
3 5
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 2053
2 4 5提示
1≤F≤V≤1001≤F≤V≤1001≤F≤V≤100
解析 花瓶
【1】 7 23 -5 -24 16
【2】 5 21 -4 10 23
【3】-21 5 -4 -20 20根据题意可知i 朵花和 i1 朵花的关系是 ii1i i1ii1 即上一朵花一定在下一朵花的左边因此 jj1j j1jj1 花瓶。
假设 dp[i][j]dp[i][j]dp[i][j] 表示第 i 朵花插在第 j 个瓶子上的美观度。
【1】 7 23 -5 -24 16
【2】 5 28 19 33 46
【3】-21 10 24 8 53因为 jj1j j 1jj1 所以 dp[i][j]dp[i][j]dp[i][j] 等于 dp[i−1][1]dp[i-1][1]dp[i−1][1] 到 dp[i−1][j−1]dp[i-1][j-1]dp[i−1][j−1] 这个闭区间之内的最大值加上 dp[i][j]dp[i][j]dp[i][j] 的美观度。
怎么说呢就是我插入了 dp[i][j]dp[i][j]dp[i][j] 这个位置那么我上一朵花的位置一定是在 dp[i−1][j−1]dp[i-1][j-1 ]dp[i−1][j−1] 的左边包含我们只需要选择这个区间内的最大值就行了。
dp[2][3] 19也就是上一朵花的美观度的最大值 (dp[1][2]23dp[1][2] 23dp[1][2]23) 加上当前插入的花瓶美观度(dp[2][3]−4dp[2][3] -4dp[2][3]−4)
我写题时遇到的坑 一直 45%因为初始化错了 for(int i 1; i F; i) {for(int j 1; j V; j) {dp[i][j] -INF;}
}这样子其实是没有初始化到第一列 dp[0][i]dp[0][i]dp[0][i] 结果就是其它的位置都是无穷小而这一列无穷大所以导致了 0 最大所以最后的答案也是 0。 3 5
7 23 -5 -24 16
-20 -20 -20 -20 -20
-20 -20 -20 -20 -20 0
0 0 0而正确答案是 -17
2 3 4初始值不够小我一开始是 int INF 0x3f; // 错误的DP 信息
子问题求 i 朵花插在第 j 个瓶子上的美观度。DP 定义第 i 朵花插在第 j 个瓶子上的美观度。DP 方程dp[i][j]max(dp[i][j],dp[i−1][k]w[i][j])dp[i][j] max(dp[i][j], dp[i-1][k] w[i][j])dp[i][j]max(dp[i][j],dp[i−1][k]w[i][j])DP 初始化dp[i][j]−INFdp[i][j] -INFdp[i][j]−INF
代码
public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int F sc.nextInt(), V sc.nextInt();int MAX 105;int[][] w new int[MAX][MAX];int[][] dp new int[MAX][MAX];int[][] path new int[MAX][MAX];int INF 0xfffffff;for(int i 1; i F; i) Arrays.fill(dp[i], -INF);dp[0][0] 0;for(int i 1; i F; i) {for(int j 1; j V; j) {w[i][j] sc.nextInt();}}for(int i 1; i F; i) {for(int j 1; j V; j) {int pos 0;// 寻找上一朵花的最大值for(int k 1; k j; k) {if(dp[i-1][k] dp[i-1][pos]) pos k;}dp[i][j] dp[i-1][pos] w[i][j];path[i][j] pos; // 保存路径}}int k 0;for(int i F; i V; i) {if(dp[F][i] dp[F][k]) k i;}System.out.println(dp[F][k]);path(F, k, path);}public static void path(int F, int k, int[][] path) {String str k ;for(int i F; i 1; i--) {str path[i][k] str;k path[i][k];}System.out.println(str);/*if(F 0) return;path(F-1, path[F][k], path);System.out.print(k );*/}
}
