Comment

71123140焦博宇: 2025-05-22 09:38:22

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<climits>
#include<iomanip>
#include<algorithm>
using namespace std;

struct activity {
	activity() {
		s = f = v = 0;
	}
	int s;
	int f;
	int v;
};
activity a[10005];
int dp[10005];

bool cmp(activity a, activity b)
{
	return a.f < b.f;
}

int main()
{
	int M;
	cin >> M;
	for (int i = 1; i <= M; i++)
	{
		int N;
		cin >> N;
		for (int i = 1; i <= N; i++)
			cin >> a[i].s >> a[i].f >> a[i].v;
		sort(a + 1, a + N + 1, cmp);
		for (int i = 1; i <= N; i++)
		{
			dp[i] = dp[i - 1];
			int j = 0;
			for (j = i - 1; a[j].f > a[i].s; j--);
			dp[i] = max(dp[i], dp[j] + a[i].v);
		}
		cout << dp[N] << endl;
	}
	return 0;
}

Huhu_Miao: 2025-05-22 09:27:48

/**
 *    author:  Huhu_Miao
 *    created: 2025.5.22 09:27:07 (UTC+8)
**/

#include<iostream>
#include<algorithm>

constexpr int N = 10001;

struct activity
{
	int s;
	int f;
	int v;

	void print(){ std::cout << s << ' '<< f << ' ' << v << '\n'; }

}activities[N];

int dp[N] , p[N];

void solve(){
	int n; std::cin >> n;
	for(int i = 1 ; i <= n ; i++) std::cin >> activities[i].s >> activities[i].f >> activities[i].v;
	std::sort(activities + 1 , activities + n + 1 , [](activity act1 , activity act2){
		return act1.f < act2.f;
	});

	for(int i = 1 ; i <= n ; i++){
		for(int j = i - 1 ; j >= 0 ; j--){
			if(activities[j].f <= activities[i].s){
				p[i] = j;
				break;
			}
		}
	}

	for(int i = 1 ; i <= n ; i++) dp[i] = std::max(dp[i-1] , dp[p[i]] + activities[i].v);
	std::cout << dp[n] << '\n';
}

int main(){
	std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
	int T; std::cin>>T;
	while(T--) solve();
	return 0;
}

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>