首页 > 代码库 > 【noi 2.6_6045】开餐馆(DP)
【noi 2.6_6045】开餐馆(DP)
题意:有N个地址,从中选一些开餐馆,要保证相邻餐馆的距离大于k。问最大利润。
解法:f[i]表示在前 i 个地址中选的最大利润。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 7 const int Maxn=110,Maxm=1000010; 8 int m[Maxn],p[Maxn]; 9 int f[Maxn];10 11 int mmax(int x,int y)12 { return x>y?x:y; }13 int main()14 {15 int T,n,w;16 scanf("%d",&T);17 while (T--)18 {19 scanf("%d%d",&n,&w);20 for (int i=1;i<=n;i++) scanf("%d",&m[i]);21 m[0]=-Maxm;22 for (int i=1;i<=n;i++) scanf("%d",&p[i]);23 f[0]=0;24 for (int i=1;i<=n;i++)25 {26 f[i]=mmax(f[i-1],p[i]);//不选第i个和只选第i个27 for (int j=1;j<i;j++)28 {29 if (m[i]-m[j]>w) f[i]=mmax(f[i],f[j]+p[i]);//上个选的为第j个30 else break;//小心判断31 }32 }33 printf("%d\n",f[n]);34 }35 return 0;36 }
【noi 2.6_6045】开餐馆(DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。