3059: 开餐馆DP

解题思路:f[i] 表示包含i点的最大利润

注意事项:

参考代码:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 1e2 + 10;
int f[N],m[N],p[N],n,t,k,pre,ans;
int main()
{
	cin >> t;
	while(t--){
		cin >> n >> k;
		memset(f,0,sizeof f);
		memset(m,0,sizeof m);
		memset(p,0,sizeof p);
		for(int i = 1; i <= n; i ++) cin >> m[i];
		for(int i = 1; i <= n; i ++) {
			cin >> p[i];
			f[i] = p[i];
		}
		for(int i = 1; i <= n; i ++){
			pre = i - 1;
			while(m[i] - m[pre] <= k && pre > 0) pre --;
			f[i] = max(f[i - 1],f[pre] + p[i]);
		}
		ans = 0;
		for(int i = 1; i <= n; i ++) ans = max(ans,f[i]);
		cout << ans  <<endl;
	}
	return 0;
}

另外一种解法（有两项测试数据未通过）：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 1e2 + 10;
int f[N],r[N],m[N],p[N],n,t,k;
int main()
{
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	cin >> t;
	while(t--){
		cin >> n >> k;
		memset(f,0,sizeof f);
		memset(m,0,sizeof m);
		memset(p,0,sizeof p);
		memset(r,0,sizeof r); 
		for(int i = 1; i <= n; i ++) cin >> m[i];
		for(int i = 1; i <= n; i ++) {
			cin >> p[i];
			f[i] = p[i];
			r[i] = p[i];
		}
		for(int i = 1; i <= n; i ++)
			for(int j = n; j >= 1; j --){
				if(abs(m[j] - m[i]) <= k) continue;
				f[j] = max(f[j], f[i] + p[j]);
			}
		for(int i = n; i >= 1; i --)
			for(int j = 1; j <= n; j ++){
				if(abs(m[j] - m[i] ) <= k) continue;
				r[j] = max(r[j], r[i] + p[j]);
			}
		cout << ((f[n] > r[1])? f[n]:r[1] )<< endl;
	}
	return 0;
}