题目链接
题目解法
\(n^3\) 的 \(dp\) 是显然的
但我们没用到 \(a\) 不降的性质
考虑一个很妙的结论：最优选法中，至多只有一个序列取了且未取满
为什么？
如果最优情况下，存在选且未选满的序列为 \(a,b\)，第一个未选的元素为 \(x,y\)
如果 \(a_x>a_{pre_y}\)，那么选 \(x\) 比选 \(pre_y\) 更优，反之同理
然后就相当于要做除了 \(i\) 的背包，直接用类似线段树分治的方法做就可以了
时间复杂度 \(O(nk\log n)\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
const int N=3100;
vector<int> vec[N];
int n,k,len[N];LL sum[N];
LL ans,knap[15][N];
void solve(int l,int r,int dep){
if(l==r){
chkmax(ans,knap[dep][k]);
LL res=0;
F(i,0,len[l]-1) if(k>=i+1) res+=vec[l][i],chkmax(ans,knap[dep][k-i-1]+res);
return;
}
int mid=(l+r)>>1;
F(i,0,k) knap[dep+1][i]=knap[dep][i];
F(i,l,mid) DF(j,k,len[i]) chkmax(knap[dep+1][j],knap[dep+1][j-len[i]]+sum[i]);
solve(mid+1,r,dep+1);
F(i,0,k) knap[dep+1][i]=knap[dep][i];
F(i,mid+1,r) DF(j,k,len[i]) chkmax(knap[dep+1][j],knap[dep+1][j-len[i]]+sum[i]);
solve(l,mid,dep+1);
}
int main(){
n=read(),k=read();
F(i,1,n){
len[i]=read();
F(j,1,len[i]){
int v=read();
vec[i].pb(v),sum[i]+=v;
}
}
solve(1,n,0);
printf("%lld\n",ans);
fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
return 0;
}