//Given a collection of segments, each segment have three values, the beginning point, the end point and the
//score. Find a set of segments have the largest score but non of them is overlapped with others.

{start point, end point, score}
比如{1,3,3}, {2,4,5}, {3,5,3}

答案是{1,3,3}，{3,5,3}，

#include <vld.h> #include <iostream> #include <memory> #include <stdlib.h> #include <queue> #include <list> #include <deque> #include <map> #include <string> #include <set>using namespace std;struct term {int beg;int end;int score;//term(int b, int e, int s) : beg(b), end(e), score(s){} };bool cmp(const term &a, const term &b) {return a.beg < b.beg; }int sumSeg(vector<term> &vec, vector<term> &col) {sort(vec.begin(), vec.end(), cmp);vector<int> dp(vec.size(), INT_MIN);vector<int> his(vec.size(), 0);int n = vec.size();int finalScore = INT_MIN;int finalIdx = -1;for (int i = 0; i < n; ++i) {int best = INT_MIN;int bestIdx = -1;for (int j = i - 1; j >= 0; --j) {if (vec[i].beg >= vec[j].end && best < dp[j]) {best = dp[j];bestIdx = j;}}if (bestIdx == -1) {dp[i] = vec[i].score;his[i] = i;}else {dp[i] = vec[i].score + best;his[i] = bestIdx;}if (finalScore < dp[i]) {finalScore = dp[i];finalIdx = i;}}int t = finalIdx;col.push_back(vec[t]);while (t != his[t]) {t = his[t];col.push_back(vec[t]);}return finalScore;}bool Cmp(const term &a, const term &b) {return a.end < b.end; }int biSearch(vector<term> &vec, int to, int key) {int beg = -1;int end = to + 1;while (beg + 1 < end) {int mid = (beg + end )/2;if (vec[mid].end <= key)beg = mid;elseend = mid;}if (beg == -1 || vec[beg].end > key)return -1;return beg; }int biMaxSeg(vector<term> &vec, vector<term> &col) {//必須保證term的score是正數(shù)sort(vec.begin(), vec.end(), Cmp);vector<int> dp(vec.size(), 0);vector<pair<int, int> > last;//first ,last; second, 1,curr,0,non-currdp[0] = vec[0].score;last.push_back(make_pair(-1,1));int n = vec.size();for (int i = 1; i < n; ++i) {dp[i] = dp[i - 1];last.push_back(make_pair(i -1, 0));int pre = biSearch(vec,i - 1, vec[i].beg);if (pre == -1){if (dp[i] < vec[i].score) {dp[i] = vec[i].score;last[i].first = -1;last[i].second = 1;}}else {if (dp[i] <= dp[pre] + vec[i].score) {dp[i] = dp[pre] + vec[i].score;last[i].first = pre;last[i].second = 1;}}}for (int i = n - 1; i != -1; ) {if (last[i].second) {col.push_back(vec[i]);}i = last[i].first;}return dp[n-1];}int main() {vector<term> vec;term arr[] = {{1, 3, 3},{2, 3, 100}, {0, 4, 2}, {3,5, 7}, {2, 6,1}, {0, 6, 2}, {2, 6, 1}, {6, 7, 3}};term tt = {5,6,7};copy(arr, arr + 8, back_inserter(vec));vector<term> idx;cout<< biMaxSeg(vec, idx)<<endl;for (int i = 0; i < idx.size(); ++i)cout <<"("<<idx[i].beg<<","<<idx[i].end<<") ";cout <<endl; }

總結(jié)

以上是生活随笔為你收集整理的找出得分最高的无重复子段的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。