itdef

地址 https://www.papamelon.com/problem/307

解答
使用動態規劃解答。dp[i]為選擇第i個區間能獲取的最大的牛奶數目
那么在i區間之前的所有區間，如果與第i個區間的時間不沖突，都可以考慮選擇
狀態方程
區間j的結束時間在 區間i的起始時間之前 且有休息間隔
dp[i] = max(dp[i]+dp[j])

代碼

#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;

const int N = 1000010;
const int M = 1010;

int n, m, r;

struct AREA {
	int start, finish;
	int eff;
}area[M];

int dp[M];

bool cmp(const struct AREA& a, const struct AREA& b) {
	if (a.finish < b.finish) { return true; }
	else if (a.finish == b.finish) {
		if (a.start > b.start) { return true; }
		else if (a.start == b.start) {
			if (a.eff > b.eff) { return true; }
		}
	}

	return false;
}


int main()
{
	while (~scanf("%d", &n)) {
		scanf("%d%d",&m,&r);
		memset(area,0,sizeof area);
		memset(dp,0,sizeof dp);
		for (int i = 1; i <= m; i++) {
			scanf("%d%d%d",&area[i].start,&area[i].finish,&area[i].eff);
		}

		sort(&area[1],&area[m]+1,cmp);
		int ans = 0;
		for (int i = 1; i <= m; i++) {
			dp[i] = area[i].eff;
			int currStart = area[i].start;
			for (int j = i-1; j > 0; j--) {
				int preEnd = area[j].finish;
				if (currStart - preEnd > r) {
					dp[i] = max(dp[i], dp[j] + area[i].eff);
				}
			}
			ans = max(ans, dp[i]);
		}

		cout << ans << endl;
	}


	return 0;
}

我的視頻題解空間