#include<bits/stdc++.h> using namespace std; int m,n; int a[11][16]; //存放数据 int f[16]; //用来第一问的推导 char c[16][16]; //16个字符串对应f[16]; //"000000...","010250..." 方便输出但不方便理解 int main() { memset(c,48,sizeof(c)); //把c变成"00000000000..."; scanf("%d%d",&n,&m); for(int i=1;i<n+1;i++) { for(int j=1;j<m+1;j++) { scanf("%d",&a[i][j]); } } //万一设备多了收益反而降了呢？ //想起了做了无数遍的一元二次方程题... int xyem=0,itp=0; for(int i=1;i<m+1;i++) { if(a[1][i]>xyem) { f[i]=a[1][i]; c[i][1]=i+48; xyem=a[1][i]; itp=i; } else { f[i]=xyem; c[i][1]=itp+48; } } for(int i=2;i<n+1;i++) { for(int j=m;j>0;j--) { //f[j]初始状态为f[j]+a[0](a[0]显然为零), //所以k不需要=j就可以包括转移方程中的所有情况; for(int k=0;k<j;k++) { //小于就可以保证字典序最小了 if(f[j]<f[k]+a[i][j-k]) { f[j]=f[k]+a[i][j-k]; strncpy(c[j],c[k],m+1); c[j][i]=c[j][i]+j-k; } } } } //以下是输出 printf("%d\n",f[m]); for(int i=1;i<n+1;i++) { printf("%d %d\n",i,c[m][i]-48); } return 0; }