链接

整体思路:

首先这题数据很小，可以进行暴力枚举，其实也就是最暴力最朴素的dp
首先dp[i][j]表示： 前i-1种花已经在1 ~ j - 1区间内选好了 并且当前第i种花要选第j个花
瓶属性是求最大值，并且题目还要求出最小字典序的具体方案
那我们完全可以倒着dp 也就是从第n个花瓶开始找 找到第1个花瓶 然后要确保当前第i种花在合
法的区间内进行选举,不难得出状态转移方程

dp[i][j] = max(dp[i][j], dp[i + 1][k] + g[i][j]; (k表示i + 1号花选的花瓶)

首先要明确一些细节，第i种花的选取区间应该为(i,m - n + i),因为这里是倒着枚举，
所以先确定好i + 1的区间范围再去选择第i种花的选取区间
第i + 1的区间范围应该是k = (i + 1, m - n + i + 1) 所以第i种花的选取范围应该是
(i,k - 1),并且k - 1最大刚好是m - n + i, 求具体方案就直接看代码 比较简单

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define ps puts("")
#define x first
#define y second
#define pb push_back
#define pp push_pop
#define IOS ios::sync_with_stdio,cin.tie(0),cout.tie(0)
using namespace std;
const int N=1e6 + 10,M=2*N+10,MOD=998244353,INF=0x3f3f3f3f;
const long long INFF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-7;
typedef long long ll;
typedef __int128 LL;
typedef pair<int,int> pii;
typedef pair<int,pii> pip;
typedef pair<int,char> pic;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<string> vs;
LL read()
{
	//直接在函数里面实现读字符串操作更简洁
	LL res=0;//初始结果赋值0
	char scan[1005];
	scanf("%s",scan);
	for(int i=0;i<strlen(scan);i++)
		res*=10,res+=scan[i]-'0';//实现进位
	return res;//返回__int128类型
}
void print(LL num)
{//递归调用，实现从高位向低位输出
	if(num>9) 
		print(num/10);
	putchar(num%10+'0');
}

ll g[101][101];
ll dp[101][101];
int n,m;
//dp[i][j] 表示前i-1种花已经在1 ~ j - 1区间内选好了 并且当前第i种花要选第j个花瓶

void solve()
{
	cin>>n>>m;
	for(int i = 1; i <= n; i ++ )
	for(int j = 1; j <= m; j ++ )
	cin>>g[i][j], dp[i][j] = - INF;
	
	for(int i = n; i >= 1; i -- )//倒着dp 先从后面选
	for(int k = i + 1; k <= m - (n - 1 - i); k ++ )//先枚举i + 1层
	for(int j = i; j < k; j ++ )//再枚举第i层
	dp[i][j] = max(dp[i][j], dp[i + 1][k] + g[i][j]);
	
	ll ans = - INF;
	for(int i = 1; i <= m; i ++ )
	ans = max(ans, dp[1][i]);
	
	cout<<ans<<endl;
	
	vector<int> v;
	int k = 1;//表示当前第i个花应该从k列开始选
	for(int i = 1; i <= n; i ++ )//因为是倒着dp所以正着选一定能保证最小字典序
	{
		for(int j = k; j <= m; j ++ )
		if(dp[i][j] == ans) {
			ans -= g[i][j];
			v.pb(j);
			k = j + 1;
			break;
		}
	}
	for(auto t : v)
	cout<<t<<" ";
}

int main()
{
	IOS;
    
	int T;
	//cin>>T; 
	T=1;	
	while(T--)
	{
		solve();
	}
	return 0;
}