二维dp挺好推 dp[i][j] = max(dp[i][j],dp[g][j-1]+o[i][i+1]-o[g][i+1])（i>g>=j-1) dp[i][j]表示第i个站台开放第j次设备 预处理出来通过i-j的人数 包括 i-1~j+1等等的 用o[i][j]表示的
没睡好 %>_<%
因为有可能全部都为0 初始化时dp设为-1.
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<queue>
using namespace std;
#define LL long long
int dp[][],q[];
int w[][],o[][],pa[][];
int main()
{
int i,j,n,k;
cin>>n>>k;
for(i = ; i < n ;i++)
{
for(j = ; j <= n-i ; j++)
{
int x;
cin>>x;
w[i][i+j] = x;
}
}
for(i = ; i <= n ; i++)
{
for(j = n ; j > i ; j--)
o[i][j] = o[i][j+]+w[i][j]+o[i-][j]-o[i-][j+];
}
memset(dp,-,sizeof(dp));
for(i = ; i < n ;i++)
dp[i][] = o[i][i+];
for(j = ; j <= k ; j++)
for(i = j; i < n; i++)
{
int kk;
for(int g = ; g < i ; g++)
{
if(dp[g][j-]+o[i][i+]-o[g][i+]>dp[i][j])
{
dp[i][j] = dp[g][j-]+o[i][i+]-o[g][i+];
kk = g;
}
}
pa[i][j] = kk;
}
int maxz=-,x;
for(i = k; i < n ; i++)
{
if(maxz<dp[i][k])
{
maxz = dp[i][k];
x = i;
}
}
cout<<maxz<<endl;
int e = ;
q[e] = x;
while(k>)
{
x = pa[x][k];
q[++e] = x;
k--;
}
sort(q+,q+e+);
for(i = ; i < e ; i++)
cout<<q[i]<<" ";
cout<<q[e]<<endl;
return ;
}
/*
5 3
5 0 6 5
5 3 7
5 3
10
44
1 2 4
4 2
5 0 6
5 3
5
19
1 2 4 3
5 0 6
5 3
5
24
1 2 3
*/