文档章节

poj_1157LITTLE SHOP OF FLOWERS

N3verL4nd
 N3verL4nd
发布于 2017/03/25 10:45
字数 870
阅读 8
收藏 0

题目:

LITTLE SHOP OF FLOWERS
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 15079   Accepted: 6961

Description

You want to arrange the window of your flower shop in a most pleasant way. You have F bunches of flowers, each being of a different kind, and at least as many vases ordered in a row. The vases are glued onto the shelf and are numbered consecutively 1 through V, where V is the number of vases, from left to right so that the vase 1 is the leftmost, and the vase V is the rightmost vase. The bunches are moveable and are uniquely identified by integers between 1 and F. These id-numbers have a significance: They determine the required order of appearance of the flower bunches in the row of vases so that the bunch i must be in a vase to the left of the vase containing bunch j whenever i < j. Suppose, for example, you have bunch of azaleas (id-number=1), a bunch of begonias (id-number=2) and a bunch of carnations (id-number=3). Now, all the bunches must be put into the vases keeping their id-numbers in order. The bunch of azaleas must be in a vase to the left of begonias, and the bunch of begonias must be in a vase to the left of carnations. If there are more vases than bunches of flowers then the excess will be left empty. A vase can hold only one bunch of flowers. 

Each vase has a distinct characteristic (just like flowers do). Hence, putting a bunch of flowers in a vase results in a certain aesthetic value, expressed by an integer. The aesthetic values are presented in a table as shown below. Leaving a vase empty has an aesthetic value of 0. 
 

V A S E S

1

2

3

4

5

Bunches

1 (azaleas)

7 23 -5 -24 16

2 (begonias)

5 21 -4 10 23

3 (carnations)

-21

5 -4 -20 20

According to the table, azaleas, for example, would look great in vase 2, but they would look awful in vase 4. 

To achieve the most pleasant effect you have to maximize the sum of aesthetic values for the arrangement while keeping the required ordering of the flowers. If more than one arrangement has the maximal sum value, any one of them will be acceptable. You have to produce exactly one arrangement. 

Input

  • The first line contains two numbers: FV.
  • The following F lines: Each of these lines contains V integers, so that Aij is given as the jth number on the (i+1)st line of the input file.


  • 1 <= F <= 100 where F is the number of the bunches of flowers. The bunches are numbered 1 through F. 
  • F <= V <= 100 where V is the number of vases. 
  • -50 <= Aij <= 50 where Aij is the aesthetic value obtained by putting the flower bunch i into the vase j.

Output

The first line will contain the sum of aesthetic values for your arrangement.

Sample Input

3 5
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20

Sample Output

53

开始没注意全为负数的情况,wa

状态转移方程:

dp[i][j] = num[i][j] + max(dp[i-1][1],dp[i-1][2],...dp[i-1][j-1]);

我们用opt定义以当前I j为结尾的花的排序的最大值,用r*(-50)表示负无穷,初始化时第一行为origin[i][j],后面为r*(-50)

Opt[][]

1

2

3

4

5

1

7

23

-5

-24

16

2

-150

-150

-150

-150

-150

3

-150

-150

-150

-150

-150

从第二行开始,对于第i行第j列,对于i>=j,遍历i-1行前j列,求出当前最大值。

Opt[][]

1

2

3

4

5

1

7

23

-5

-24

16

2

-150

21+7

-4+max(7,23)

10+max(7,23,-24)

23+max(…)

3

-150

-150

-150

-150

-150

I=3:

Opt[][]

1

2

3

4

5

1

7

23

-5

-24

16

2

-150

28

19

33

46

3

-150

-150

-4+max(-150,28)

-20+max()

20+max(-150,28,19,33)


题解:

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
	freopen("in.txt","r",stdin);
	int num[105][105];
	int dp[105][105];
	int n, m, i, j;
	cin >> n >> m;
	for(i = 1; i <= n; i++)
	{
		for(j = 1; j <= m; j++)
		{
			cin >> num[i][j];
		}
	}

	for(i = 1; i <= n; i++)
	{
		for(j = 1; j <= m; j++)
		{
			if(i == 1) dp[1][j] = num[1][j];
			else dp[i][j] = -50 * n;
		}
	}

	for(i = 2; i <= n; i++)
	{
		for(j = 1; j <=m; j++)
		{
			if(j >= i)
			{
				for(int k = 1; k < j; k++)
				{
					if(dp[i][j] < dp[i-1][k] + num[i][j])
						dp[i][j] = dp[i-1][k] + num[i][j];
				}
			}
		}
	}
	int ans = -999999;
	for(i = 1; i <= m; i++)
	{
		ans = max(ans, dp[n][i]);
	}
	cout << ans << endl;
}



© 著作权归作者所有

下一篇: usaco1.1
N3verL4nd
粉丝 1
博文 379
码字总数 481243
作品 0
朝阳
私信 提问
【POJ - 3262】Protecting the Flowers(贪心)

Protecting the Flowers 直接中文 Descriptions FJ去砍树,然后和平时一样留了 N (2 ≤ N ≤ 100,000)头牛吃草。当他回来的时候,他发现奶牛们正在津津有味地吃着FJ种的美丽的花!为了减少后...

Sky丨Star
08/05
0
0
算法进阶路径

第一阶段:练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码, 因为太常用,所以要练到写时不用想,10-15分钟内打完,甚至关掉显示器都可以把程序打 出来. 1.最短路(Fl...

暖冰
2016/04/02
155
1
ELisp编程六:定义变量

给变量赋值 set (set arg1 arg2) 这种语法将arg2设置为arg1的值 比如: 这是创建了一个symbol flowers,将(rose violet daisy buttercup) list 赋值给了flowers的value域。 稍后,可以直接使...

长平狐
2012/08/28
181
0
【Leetcode】605. Can Place Flowers

Description Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete ......

xiagnming
2018/07/30
0
0
一个搞ACM需要掌握的算法

ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红,发挥自己的长处,这才是重要的. 第一阶段:练经典常用...

long0404
2015/06/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

CentOS7.6中安装使用fcitx框架

内容目录 一、为什么要使用fcitx?二、安装fcitx框架三、安装搜狗输入法 一、为什么要使用fcitx? Gnome3桌面自带的输入法框架为ibus,而在使用ibus时会时不时出现卡顿无法输入的现象。 搜狗和...

技术训练营
今天
3
0
《Designing.Data-Intensive.Applications》笔记 四

第九章 一致性与共识 分布式系统最重要的的抽象之一是共识(consensus):让所有的节点对某件事达成一致。 最终一致性(eventual consistency)只提供较弱的保证,需要探索更高的一致性保证(stro...

丰田破产标志
今天
7
0
docker 使用mysql

1, 进入容器 比如 myslq1 里面进行操作 docker exec -it mysql1 /bin/bash 2. 退出 容器 交互: exit 3. mysql 启动在容器里面,并且 可以本地连接mysql docker run --name mysql1 --env MY...

之渊
今天
7
0
python数据结构

1、字符串及其方法(案例来自Python-100-Days) def main(): str1 = 'hello, world!' # 通过len函数计算字符串的长度 print(len(str1)) # 13 # 获得字符串首字母大写的...

huijue
今天
5
0
PHP+Ajax微信手机端九宫格抽奖实例

PHP+Ajax结合lottery.js制作的一款微信手机端九宫格抽奖实例,抽奖完成后有收货地址添加表单出现。支持可以设置中奖概率等。 奖品列表 <div class="lottery_list clearfix" id="lottery"> ......

ymkjs1990
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部