黄骅市怎么读_广州市工贸技师学院_chatgpt入口_seo交流qq群

DP加双指针解法：200ms

1.第一种

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int a[105], b[105], f[105];
int main(){int t; cin >> t;while(t--){int n, k; cin >> n >> k;for(int i = 0; i < n; i++) cin >> a[i];for(int i = 0; i < n; i++) cin >> b[i];f[0] = b[0];int ans = 0;for(int i = 1; i < n; i++){f[i] = b[i];for(int j = i - 1; j >= 0; j--)if(a[i] > a[j] + k) f[i] = max(f[i], f[j] + b[i]);else f[i] = max(f[j], f[i]);}//for(int i = 0; i < n; i++) ans = max(ans, f[i]);cout << f[n-1] << endl;}return 0;
}

2.第二种

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int a[105], b[105], f[105];
int main(){int t; cin >> t;while(t--){int n, k; cin >> n >> k;for(int i = 0; i < n; i++) cin >> a[i];for(int i = 0; i < n; i++) cin >> b[i];f[0] = b[0];int ans = 0;for(int i = 1; i < n; i++){f[i] = b[i];for(int j = i - 1; j >= 0; j--)if(a[i] > a[j] + k) f[i] = max(f[i], f[j] + b[i]);}for(int i = 0; i < n; i++) ans = max(ans, f[i]);cout << ans << endl;}return 0;
}