典型的給出區間任務和效益值,然後求最大效益值的任務取法。
屬於一維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; }