记得关注
```cpp
#include<bits/stdc++.h>
using namespace std;
int f,v;
int a[101][101];
int dp[101][101];
void print(int i, int j)
{
if(j==0)
return;
for(int k=0;k<=i-j;k++)
if(dp[i][j]==dp[j+k-1][j-1]+a[j][j+k])
{
print(j+k-1,j-1);
printf("%d ",j+k);
break;
}
}
int main()
{
scanf("%d%d",&f,&v);
for(int i=1;i<=f;i++)
{
for(int j=1;j<=v;j++)
scanf("%d",&a[i][j]);
}
for(int i=1;i<=f;i++)
dp[i][i]=dp[i-1][i-1]+a[i][i];
for(int i=1;i<=v;i++)
for(int j=1;j<=f;j++)
{
dp[i][j]=-1*0x3f3f3f3f;
for(int k=0;k<=i-j;k++)
dp[i][j]=max(dp[i][j],dp[j+k-1][j-1]+a[j][j+k]);
}
printf("%d\n",dp[v][f]);
print(v,f);
}
by AlexSong @ 2024-01-29 11:40:21