2.6基本算法之动态规划6045:开餐馆

描述

北大信息学院的同学小明毕业之后打算创业开餐馆.现在共有n 个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这 n 个地点排列在同一条直线上。我们用一个整数序列m1, m2, ... mn 来表示他们的相对位置。由于地段关系,开餐馆的利润会有所不同。我们用pi 表示在mi 处开餐馆的利润。为了避免自己的餐馆的内部竞争,餐馆之间的距离必须大于k。请你帮助小明选择一个总利润最大的方案。

答案:

#include<bits/stdc++.h>
using namespace std;
int f[1000005];//f[i]:从第1个位置到开第i个位置开餐馆能获得的最大利润 
int m[1000005];//每个餐馆开的位置 
int p[1000005];//每个餐馆的利润 
int main(){
	int t,n,k;
	cin>>t;
	while(t--){
		cin>>n>>k;
		for(int i=1;i<=n;i++){
			cin>>m[i]; 
		}
		for(int i=1;i<=n;i++){
			cin>>p[i];
		}
		memset(f,0,sizeof(f));
		//边界条件:只有一个地点,只开一家店 
		f[1]=p[1];
		//n个地点开很多家店 
		for(int i=1;i<=n;i++){//地点 
			f[i]=max(p[i],f[i-1]);//n个地点开一家店 
			for(int j=1;j<i;j++){//从j个地点到第i个地点开餐馆 
				if(m[i]-m[j]>k){
					f[i]=max(p[i]+f[j],f[i]);
				}
			}
		}
		cout<<f[n]<<endl;
	}
	return 0;
}