POJ 3616 Milking Time DP題解

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