链接

整体思路:
首先这题数据很小,可以进行暴力枚举,其实也就是最暴力最朴素的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;
}