## poj_1157LITTLE SHOP OF FLOWERS 原

N3verL4nd

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``

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

 Opt[][] 1 2 3 4 5 1 7 23 -5 -24 16 2 -150 -150 -150 -150 -150 3 -150 -150 -150 -150 -150

 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;
}``````

### N3verL4nd

【POJ - 3262】Protecting the Flowers（贪心）

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

Sky丨Star
08/05
0
0

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

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

long0404
2015/06/24
0
0

CentOS7.6中安装使用fcitx框架

3
0
《Designing.Data-Intensive.Applications》笔记 四

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