public static void main(String[] args){ int n,m,c; n=sc.nextInt(); m=sc.nextInt(); for(int i=0 ; i<n ; i++ ){ int sum=0;// 求该层的物品价值总和 c=sc.nextInt(); for(int j=0 ; j<c ; j++ ){ a[j] = sc.nextInt(); sum+=a[j]; } Arrays.fill(val,0); for(int k=1 ; k<=c ; k++){ // 当前层获得k件物品可得的最大值存入val int index= 0 , now = 0;// 滑动窗口，窗口大小为c-k while(index < c-k)// 初始窗口 从第一个开始累加 now +=a[index++]; val[k] = Math.max(val[k],sum-now); while(index<c){ // 开始往右边移动 now+= a[index]; now-=a[index-(c-k)]; val[k] = Math.max(val[k],sum-now); //求的是窗口以外的数和最大值 index++; } } // 此时该层的val已经求出 01背包求解 for(int j=m ; j>0 ; j--){ for(int k=1 ; k<= Math.min(j,c) ; j++ ) dp[j] = Math.max(dp[j],dp[j-k]+val[k]); } } System.out.println(dp[m]); }