美女网站在线免费欧美精品,在线亚洲成人,国产精品自拍网站

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 英雄哪里出來閱讀(247) 評論(0) 編輯收藏引用所屬分類: ACM

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: Zju 3170 7 Levels of Binary Search Tree (BST 應用) Pku 3140 Contestants Division (無向圖割邊+樹形DP) Pku 2777 Count Colors(線段樹) Pku 3468 A Simple Problem With Integers(線段樹) Pku 3368 Frequent Values (線段樹) hust 1017 Exact Cover (Dancing Links) HDU 1560 DNA sequence (IDA*) Pku 1383 Labyrinth && Zju 3172 Extend 7-day Vacation (最長路) Hdu 2363 Cycling(最短路) Pku 3346 Treasure of the Chimp Island (Bfs)

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

英雄哪里出來

Pku 1157 LITTLE SHOP OF FLOWERS (DP)

導航

常用鏈接

留言簿(22)

隨筆分類(102)

文章分類(22)

ACM

搜索

積分與排名

最新評論