闫氏dp分析法
import java.io.*;
import java.util.*;
public class Main{
static int N = 110,V = 110,INF = 0x3f3f3f3f;
static int[][] f = new int[N][V];
static int[][] w = new int[N][V];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int v = sc.nextInt();
for(int i = 1;i<N;i++)
Arrays.fill(f[i],-INF);
for(int i = 1;i<=n;i++)
for(int j = 1;j<=v;j++)
w[i][j] = sc.nextInt();
for(int i = 1;i<=n;i++)
for(int j = i;j<=v;j++){
for(int k = i-1;k<j;k++){
f[i][j] = Math.max(f[i][j],f[i-1][k]);
}
f[i][j] += w[i][j];
}
int ans = -INF;
int jdx = 0;
int idx = n;
for(int i = n;i<=v;i++)
if(f[n][i]>ans){
ans = f[n][i];
jdx = i;
}
System.out.println(ans);
int[] path = new int[n+2];
int k = -1;
while(idx!=0){
path[++k] = jdx;
for(int i = 1;i<jdx;i++)
if(f[idx][jdx] == f[idx-1][i]+w[idx][jdx]){
jdx = i;
break;
}
idx--;
}
for(int i = k;i>=0;i--)
System.out.print(path[i]+" ");
}
}