用一维数组f[i]表示从前i个物品里面选位置，且选择的位置距离大于k的方案的集合
很明显采用一维数组的方式进行求解
求max，数组初始化应该是单独选择每一个商店的利润的价格
但是选择一个商店的时候还需要考虑在他之前的商店的距离，是利润达到最大值

package dp;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

public class 开餐馆 {

    /**
     * @param args
     * @throws IOException 
     * @throws NumberFormatException 
     */
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
     BufferedReader buff=new BufferedReader(new InputStreamReader(System.in));
     int t=Integer.parseInt(buff.readLine());
     while(t>0){
         t--;
         String string[]=buff.readLine().split(" ");
         int n=Integer.parseInt(string[0]);
         int k=Integer.parseInt(string[1]);
         int a[]=new int [n+1];
          string=buff.readLine().split(" ");
          for(int i=1;i<=n;i++)a[i]=Integer.parseInt(string[i-1]);
          int pri[]=new int [n+1];
          string=buff.readLine().split(" ");
          for(int i=1;i<=n;i++)pri[i]=Integer.parseInt(string[i-1]);

          int f[]=new int [n+1];
          //n*n
          /*for(int i=1;i<=n;i++){
              f[i]=pri[i];
              for(int j=1;j<=i;j++){
                  if(a[i]- a[j] >k) {
                      f[i]= Math.max(f[i],f[j]+pri[i]);
                  }
              }

          }*/

          //双指针算法
          int j=1;
          int ma=0;
          for(int i=1;i<=n;i++){
              f[i]=pri[i];
              while(a[i] -a[j] >k){//可能存在不止一个a[j],使得差值大于k
                  f[i]=Math.max(f[i], f[j]+pri[i]);
                  j++;
              }
            ma=Math.max(f[i], ma);
          }
      System.out.println(ma);
     }

    }

}