@[K__J__M](/user/958293) 改成`dp`，即可
by danlao @ 2024-01-30 08:32:48
《优化》
by sunzhaoyang @ 2024-01-30 08:35:21
我觉得我不会优化。
~~什么不会，我为什么要帮你？等等，AC代码？OKOK，直接抄。~~
by kexiye @ 2024-01-30 08:58:17
可以结合辅助输出理解dp
代码：[language:C]
```c
n,m,a[11][16],f[11][16],con[11][16][16],i,j,k,h; //qian i ge has j, qian i-1 has k, so i has j-k
main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;++i)for(j=1;j<=m;++j)scanf("%d",&a[i][j]);
for(i=1;i<=n;++i)for(j=0;j<=m;++j)for(k=0;k<=j;++k){
if(f[i-1][k]+a[i][j-k]>f[i][j]){
f[i][j]=f[i-1][k]+a[i][j-k]; printf("(i,j):%d %d Matrix:\n",i,j);
for(int d=1;d<=i;++d,puts(""))for(int e=1;e<=j;++e)printf("%d ",f[d][e]);
for(h=1;h<i;++h)con[i][j][h]=con[i-1][k][h];//i,j,1=>1,j,1,con[i-1][k][i-2]: con[i-2][k-con[i-1][k][i-1]][i-2] //actually this
con[i][j][i]=j-k;//con: qian i ge, gong j ge,
printf("Travers: ");
for(int d=1;d<=i;++d) printf("%d ",con[i][j][d]);puts("");
}
}
printf("%d\n",f[n][m]);
for(i=1;i<=n;++i)printf("%d %d\n",i,con[n][m][i]);
}
```
by cat_lover1 @ 2024-02-03 09:16:19