程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 3616 Milking Time DP題解

POJ 3616 Milking Time DP題解

編輯:C++入門知識

POJ 3616 Milking Time DP題解


典型的給出區間任務和效益值,然後求最大效益值的任務取法。

屬於一維DP了。

一維table記錄的數據含義:到當前任務的截止時間前的最大效益值是多少。

注意, 這表示當前任務一定要選擇,但是最終結果是不一定選擇最後一個任務,故此最後需要遍歷找到table數組的最大值,當然計算過程中使用一個數記錄最終最大值也是可以的。

狀態轉移方程就是: tbl[i] = MAX({from tbl[0]->tbl[i-1] }+ weight[i] ),即區間0到i-1加上i的當前效益值。

#include 
#include 
#include 
using std::sort;

const int MAX_M = 1001;
const int MAX_N = 1000001;
int N, M, R;

struct Interval
{
	int sta, end, effi;
	bool operator<(const Interval &i) const
	{
		return end < i.end;
	}
};
Interval inter[MAX_M];
long long tbl[MAX_M];

inline long long max(long long a, long long b) { return a > b ? a : b; }

long long getMaxEffi()
{
	if (M < 1) return 0LL;
	long long maxEffi = 0;
	sort(inter, inter+M);
	for (int i = 0; i < M; i++)
	{
		tbl[i] = inter[i].effi;
		for (int j = 0; j < i; j++)
		{
			if (inter[j].end <= inter[i].sta)
				tbl[i] = max(tbl[i], tbl[j]+inter[i].effi);
		}
		maxEffi = max(maxEffi, tbl[i]);
	}
	return maxEffi;
}

int main()
{
	while (scanf("%d %d %d", &N, &M, &R) != EOF)
	{
		for (int i = 0; i < M; i++)
		{
			scanf("%d %d %d", &inter[i].sta, &inter[i].end, &inter[i].effi);
			inter[i].end += R;
		}
		printf("%lld\n", getMaxEffi());
	}
	return 0;
}



  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved