Comment

hanser414627925: 2024-05-29 15:25:28

//不是贪心，而是dp
#include<iostream>
using namespace std;
void QuickSort(int a[], int x, int y);
void Swap(int& x, int& y);
int* s = new int[10000], * f = new int[	10000], * v = new int[10000];
//其中si表示活动开始时间，fi表示活动的结束时间，vi表示活动的权重,si < fi
int main()
{
	int m, n, k;
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> n;
		for (int j = 0; j < n; j++)
			cin >> s[j] >> f[j] >> v[j];
		QuickSort(f, 0, n - 1);	//sort by end time
		int* max = new int[n],*p=new int[n];	
		for (int j = 0; j < n; j++)
		{
			max[j] = 0; p[j] = -1;
		}
		for (int j = 0; j < n; j++)
			for (int t = j - 1; t >= 0; t--)
				if (s[j] >= f[t])
				{
					p[j] = t;//使得活动t与j相容的最大标记,t<j
					break;
				}
		for (int j = 0; j < n; j++)
			if(p[j]!=-1)
				max[j] = (max[j - 1] > max[p[j]] + v[j] ? max[j-1] : max[p[j]] + v[j]);
			else max[j] = (max[j - 1] > v[j] ? max[j - 1] :  v[j]);
		cout << max[n-1] << endl;
	}
	return 0;
}
void QuickSort(int a[], int x, int y)
{
	if (x >= y)return;
	int pivot = a[x], pivotpos = x;
	for (int i = x; i <= y; i++)
	{
		if (a[i] < pivot)
		{
			pivotpos++;
			if (pivotpos != i)			//小于基准的交换到左侧
			{
				Swap(a[pivotpos], a[i]);
				Swap(s[pivotpos], s[i]);
				Swap(v[pivotpos], v[i]);
			}
		}
	}
	Swap(a[x], a[pivotpos]);
	Swap(s[x], s[pivotpos]);
	Swap(v[x], v[pivotpos]);
	QuickSort(a, x, pivotpos - 1);
	QuickSort(a, pivotpos + 1, y);
}
void Swap(int& x, int& y)
{
	int temp = x;
	x = y;
	y = temp;
}

Westbrook: 2024-05-24 12:12:32

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1e5 + 10;
int f[N]; // 动态规划数组

struct Range {
    int s, f, v;
    bool operator<(const Range& M) const {
        return f < M.f;
    }
} range[N];

int main() {
    int m;
    cin >> m;
    while (m--) {
        memset(f, 0, sizeof(f));
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> range[i].s >> range[i].f >> range[i].v;
        }
        sort(range + 1, range + n + 1);

        for (int i = 1; i <= n; i++) {
            f[i] = max(f[i - 1], range[i].v); // 初始化为不选择当前活动的最大值
            for (int j = i - 1; j > 0; j--) {
                if (range[j].f <= range[i].s) {
                    f[i] = max(f[i], f[j] + range[i].v); // 选择当前活动，并加上不冲突的最大值
                }
            }
        }

        cout << f[n] << endl; // 输出最大值
    }
    return 0;
}贪心＋动态规划即可，记得不选当前活动的时候初始化要把自身算上，所以动态规划有三种情况，一种不选自己，只选自己，选自己

tom_pan: 2024-05-17 11:00:34

<script id="123"></script>