C. No Bug No Game
\(很简单的一个dp\)
\(在枚举到当前为i的时候假设当前容量为j 对其进行转移\)
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int mod = 998244353;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; };
int qpw(int a, int b) {
int ans = 1;
while (b) {
if (b & 1)ans = ans * a % mod;
a = a * a % mod, b >>= 1;
}
return ans;
}
int inv(int x) { return qpw(x, mod - 2); }
const int N=3e3+10;
int dp[N][N][5];
void solve(){
int n,k;
cin>>n>>k;
int sum=0;
vector p(n+1,vector<int>());
for(int i=1;i<=n;i++){
int t;
cin>>t;
sum+=t;
p[i].resize(t+1);
for(int j=1;j<=t;j++)cin>>p[i][j];
}
if(sum<=k){
// assert(0);
int ans=0;
for(int i=1;i<=n;i++){
int t=p[i].size()-1;
ans+=p[i][t];
}
cout<<ans<<'\n';
return;
}
memset(dp,~0x3f,sizeof dp);
dp[0][0][1]=0;
dp[0][0][0]=0;
for(int i=1;i<=n;i++){
int t=p[i].size()-1;
for(int j=0;j<=k;j++){
dp[i][j][0]=dp[i-1][j][0];
dp[i][j][1]=dp[i-1][j][1];
if(j>=t){
dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j-t][0]+p[i][t]);
dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-t][1]+p[i][t]);
}
for(int z=1;z<t;z++){
if(j>=z){
dp[i][j][0]=max(dp[i][j][0],dp[i-1][j-z][1]+p[i][z]);
}
}
}
}
cout<<max(dp[n][k][1],dp[n][k][0])<<'\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int _ = 1;
// cin >> _;
while (_--)solve();
}