大疆笔试 最优收费方案_大疆无人机飞丢数据分析收费吗

典型的动态规划问题，不过一些细节处理起来还是很糟心的，可以参考https://www.cnblogs.com/leokale-zz/p/12381855.html的解析

现在有一个服务收费方案:在时间段1st<6内，每单位时间收费为10元;在时间段
6st<10内，每单位时间收费为5元;在时间段tz10,每单位时间收费为2元。该服务
同时只能为一个用户服务，假如有一批用户都需要请求该服务，请编写一段程
序，选择出若干用户请求进行服务，使得总的收费达到最多，并打印出依次服务
的用户编号。

输入描述
输入数据有1行，包含每个用户的编号、开始服务时间和结束服务时间(中
间以空格隔开，用户间以逗号和空格隔开)。上面例子的输入如下:
114.226,3312.4610
“1 1 4"中的第1个1代表用户编号为1,第2个1代表的是开始服务时间，4代
表结束服务时间，总的服务时间为4 -1-3,对应的费用为(4 1)*10-30;
“22 6"中的第1个2代表用户编号为2,第2个2代表的是开始服务时间，6代
表结束服务时间，总的服务时间为6 2=4,对应的费用为(6- 2)*10=40;
"33 12"中的第1个3代表用户编号为3，第2个3代表的是开始服务时间，12
代表结束服务时间，总的服务时间为12- 3=9，对应的费用为(6-3)*10+(10-
6)*5+(12-10)*2=54;
“46 10”中的4代表用户编号为4，6代表的是开始服务时间，10代表结束服
务时间，总的服务时间为10-6-4, 对应的费用为(10-6)*5-20。
输出描述
60,24
其中，60代表的是最多的总费用(其中包括用户2的40和用户4的20) 中间
以逗号和空格隔开，*2 4"代表的是依次服务的用户编号。
样例输入
1 1 4.226,3312, 4610
样例输出
60,24
 

/*功能：*/
#include "./stdc++.h"
 
using namespace std;
 
int monye(int start, int end) {
	int res = 0;
	if (end < 6) {
		return (end - start) * 10;
	}
	if (end < 10) {
		if (start < 6) {
			res += (6 - start) * 10;
		}
		res += (end - 6) * 5;
	}
	if (end >= 10) {
		if (start < 6) {
			res += (6 - start) * 10;
			res += 4 * 5;
		}
		else if (start < 10) {
			res += (10 - start) * 5;
		}
		res += (end - 10) * 2;
	}
	return res;
}
 
int main() {
	string line = "1 1 4, 2 2 6, 3 3 12, 4 6 10";
	// cin>> line;
	// cout<< "60, 2 4"<<endl;
	string item;
	// getline(cin,line);
	// cout<< line<<endl;
	istringstream items(line);
	deque<string> st1;
	stack<string> st2;
	vector<vector<int>> vec;
	int cnt = 1;
 
	vector<int> tmp(3);
	while (items >> item)
	{
		switch (cnt)
		{
		case 1:
			tmp[0] = atoi(item.c_str());
			cnt++;
			break;
		case 2:
			tmp[1] = atoi(item.c_str());
			cnt++;
			break;
		case 3:
			cnt = 1;
			if(item[item.size() - 1] == ',')
				tmp[2] = atoi(item.erase(item.size() - 1).c_str());
			else
			{
				tmp[2] = atoi(item.c_str());
			}
			vec.push_back(tmp);
		default:
			break;
		}
	}
	int n = vec.size();
	vector<int> dp(n, 0);
	vector<int> pre(n, 0);
	vector<vector<int>> id;
	for (int i = n - 1; i >= 0; --i) {
		for (int j = i - 1; j >= 0; --j) {
			if (vec[j][2] <= vec[i][1]) {
				pre[i] = j;
				break;
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		if (i == 0) {
			dp[i] = monye(vec[i][1], vec[i][2]);
			vector<int> tmp;
			tmp.push_back(vec[i][0]);
			id.push_back(tmp);
			continue;
		}
		if (pre[i] == 0) {
			int tmpMonye = monye(vec[i][1], vec[i][2]);
			if (tmpMonye > dp[i - 1]) {
				dp[i] = tmpMonye;
				vector<int> tmp;
				tmp.push_back(vec[i][0]);
				id.push_back(tmp);
			}
			else {
				dp[i] = dp[i - 1];
				vector<int> id_tmp;
				for (auto num : id[i - 1]) {
					id_tmp.push_back(num);
				}
				id.push_back(id_tmp);
			}
		}
		else {
			int tmpMonye = monye(vec[i][1], vec[i][2]) + dp[pre[i]];
			if (tmpMonye > dp[i - 1]) {
				dp[i] = tmpMonye;
				vector<int> id_tmp;
				for (auto num : id[pre[i]]) {
					id_tmp.push_back(num);
				}
				id.push_back(id_tmp);
				id[id.size() - 1].push_back(vec[i][0]);
			}
			else {
				dp[i] = dp[i - 1];
				vector<int> id_tmp;
				for (auto num : id[i - 1]) {
					id_tmp.push_back(num);
				}
				id.push_back(id_tmp);
			}
		}
	}
	cout << dp[dp.size() - 1] << ", ";
	for (auto i : id[id.size() - 1]) {
		cout << i << " ";
	}
	return 0;
}
// hello undo redo world.
//1 1 4, 2 2 6, 3 3 12, 4 6 10