谁有思加P1473题解

#include <bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;
int n, m, a[21], f[21], maxx;
int ans = inf;

int Max () {
	int maxn = -inf;
	for (int i = 1; i <= m; i++) maxn = max(maxn, f[i]);
	return maxn;
}

void dfs (int c, int ma) {
	if (ma > ans) 
		return;
		
	if (c == n+1) {
		ans = min(ans, ma);
		return;
	}
	
	for (int i = 1; i <= m; i++) {
		f[i] += a[c];
		if(Max()<ans){
			dfs(c+1,max(ma,f[i]));
		}
		// else break;
		f[i]-=a[c];
	}
}

bool cmp (int x, int y) {
	return x>y;	
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		// ans+=a[i];
	}
	sort(a+1,a+n+1,cmp);
	dfs(1,0);
	cout<<ans;	
	return 0;
}

2024stu054 你那是那题？ 为什么是WA的

//10pts
#include <bits/stdc++.h>
using namespace std;

const long long inf = 0x3f3f3f3f;

const int N = 3e4 + 5;
int n, k;
struct node {
	int p;
	int t;
} a[N];
int start[N];
int dp[N];

int main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> k;
	for (int i = 1; i <= k; i++) {
		int end;
		cin >> a[i].p >> end;
		a[i].t = end - a[i].p + 1;
		start[a[i].p]++;
		n = max(n, end);
	}
	
	for (int i = n; i >= 1; i--) {
		if (start[i] == 0) {
			dp[i] = dp[i+1]+1;
		}
		else {
			for (int j = 1; j <= k; j++) {
				if (a[j].p == i)
					dp[i] = max(dp[i], dp[i + a[j].t]);
			}
		}
	}
	
	cout << n - dp[1];
	return 0;
}

文明放题解，请不要放错误或不好Copy的代码。

马牛逼