题意：有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 ",f[n]); 34 } 35 return 0; 36 }