这边也是用DP做出来了(一眼01背包)
查看原帖
这边也是用DP做出来了(一眼01背包)
1475762
xiaoyingjie1楼主2025/1/22 18:48
#include <bits/stdc++.h>
using namespace std;
int n, dp[50005], maxa;
struct node{
	int a,b;
}s[505];
bool cmp(node x, node y){
	return x.a < y.a;
}
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> s[i].a;
    for(int i = 1; i <= n; i++) cin >> s[i].b;
    sort(s + 1, s + n + 1, cmp);
    for(int i = 1; i <= n; i++){
    	for(int j = s[i].a; j >= 1; j--){
    		dp[j] = max(dp[j], dp[j - 1] + s[i].b);
		}
	}
	for(int i = 1; i <= n; i++) maxa = max(maxa, dp[i]);
	cout << maxa << endl;
    return 0;
}
2025/1/22 18:48
加载中...