随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

Pku 1157 LITTLE SHOP OF FLOWERS (DP)

问题描述：
给出一个矩阵，要求取数，每一行取一个，并且满足下一行取的数的列数要大于前一行取的列数，使得最后总和最大。
 

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

如上表，则取23 + 10 + 20 = 53
解题思路：
该题满足最优子结构，于是有DP解法。
首先定义：
map[i][j] 表示第i行第j列的值
dp[i][j]   表示到第i行为止取map[i][j]时的最优解
 则有状态转移方程：dp[i][j] = max{dp[i-1][k] + map[i][j], 1 <= k < j}

代码如下：
#include <iostream>

using namespace std;

int map[101][101];
int dp[101][101];
int f, v;

int main()
{
    int i, j, k;

    while(scanf("%d %d", &f, &v) != EOF)
    {
        int Max = -1000000;
        for(i = 1; i <= f; i++)
        {
            for(j = 1; j <= v; j++)
            {
                scanf("%d", &map[i][j]);
            }
        }

        for(i = 0; i <= f; i++)
            for(j = 0; j <= f; j++)
                dp[i][j] = -10000000;

        for(i = 1; i <= v; i++)
            dp[1][i] = map[1][i];

        for(i = 2; i <= f; i++)
        {
            for(j = i; j <= v; j++)
            {
                dp[i][j] = -10000000;
                for(k = 1; k < j; k++)
                {
                    if(map[i][j] + dp[i-1][k] > dp[i][j])
                        dp[i][j] = map[i][j] + dp[i-1][k];
                }
            }
        }

        for(i = 1; i <= v; i++)
        {
            if(dp[f][i] > Max)
                Max = dp[f][i];
        }

        printf("%d\n", Max);
    }
}


posted on 2009-02-09 15:32 英雄哪里出来 阅读(223) 评论(0)  编辑 收藏 引用 所属分类: ACM


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理