ABC-383-F - Diversity · znzryb
## 思路讲解
[ABC-390-E - Vitamin Balance](/2025/01/29/20250129-358594cd)
我感觉很像这道题，因为我就只要背包分成几块就好了
但是又有点问题，合起来的过程需要枚举非常多次，那道题只要合并3个背包就好了，我们要合并500个背包，想想就TLE
所以这种问题一般就别想裸的背包合并，需要使用类似于向斜下方走的dp
比较简单的来讲，类似于[CF-994-D. Shift + Esc （多变量优化dp）](/2025/01/05/20250105-3d295a05)
需要关注一下颜色之间的转移以及最优状态
```cpp
FOR(i,1,idx){
FOR(j,Len[i].fi,Len[i].se){
ll yen=T[j].yen,val=T[j].u;
ROF(k,Vol,1){
if(k<yen){
dp[i][k]=max(dp[i-1][k],dp[i][k]);
}else{
dp[i][k]=max({dp[i][k],dp[i][k-yen]+val,dp[i-1][k-yen]+K+val,dp[i-1][k]});
}
}
}
}
cout<<dp[idx][Vol]<<'\n';
```
## AC代码
AC
[https://atcoder.jp/contests/abc383/submissions/62392605](https://atcoder.jp/contests/abc383/submissions/62392605)
```cpp
// Problem: F - Diversity
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2024（AtCoder Beginner Contest 383）
// URL: https://atcoder.jp/contests/abc383/tasks/abc383_f
// Memory Limit: 1024 MB
// Time Limit: 2500 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=510,INF=static_cast<ll>(5e18)+3;
ll N,Vol,K;
arr A[MAXN];
// color volume
ll dp[MAXN][50010]; // most utility
inline bool cmp(arr a,arr b){ // 按照颜色排序
return a[2]<b[2];
}
struct Things{
ll yen,u,c;
}T[MAXN];
pll Len[MAXN];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>N>>Vol>>K;
// SumUtility+TdifferentColor*K
FOR(i, 1, N){ // yen Utility color
cin>>A[i][0]>>A[i][1]>>A[i][2];
}
sort(&A[1],&A[N+1],cmp);
ll idx=0;
T[1].yen=A[1][0],T[1].u=A[1][1],T[1].c=++idx;
FOR(i,2,N){
if(A[i-1][2]!=A[i][2]){ // 重新映射颜色
T[i].c=++idx;
}else{
T[i].c=idx;
}
T[i].yen=A[i][0],T[i].u=A[i][1];
}
Len[1].fi=1;
Len[idx].se=N;
FOR(i,2,N){
if(T[i].c!=T[i-1].c){
Len[T[i-1].c].se=i-1;
Len[T[i].c].fi=i;
}
}
FOR(i,1,idx){
FOR(j,Len[i].fi,Len[i].se){
ll yen=T[j].yen,val=T[j].u;
ROF(k,Vol,1){
if(k<yen){
dp[i][k]=max(dp[i-1][k],dp[i][k]);
}else{
dp[i][k]=max({dp[i][k],dp[i][k-yen]+val,dp[i-1][k-yen]+K+val,dp[i-1][k]});
}
}
}
}
cout<<dp[idx][Vol]<<'\n';
return 0;
}
/*
AC
https://atcoder.jp/contests/abc383/submissions/62392605
*/
```
## 心路历程（WA，TLE，MLE……）
记忆化搜索超时
这个时间复杂度可以这么估计，每个combDp都是由 `ROF(i,Vol-usedVol,0)` 生成的，空间乘以这个循环次数自然就是时间复杂度了
```cpp
// memorized search
ll dfs(ll curCol,ll usedVol){
if(curCol>colLim) return 0;
if(usedVol>=Vol) return 0;
if(combDp[curCol][usedVol]!=-1) return combDp[curCol][usedVol];
ll res=0;
ROF(i,Vol-usedVol,0){
ll lres=0;
if(dp[curCol][i]==0){
lres=dfs(curCol+1,usedVol);
res=max(lres,res);
break;
}
lres=dp[curCol][i]+K;
lres+=dfs(curCol+1,usedVol+i);
res=max(lres,res);
}
combDp[curCol][usedVol]=res;
return res;
}
```
[https://atcoder.jp/contests/abc383/submissions/62385966](https://atcoder.jp/contests/abc383/submissions/62385966)
```cpp
// Problem: F - Diversity
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2024（AtCoder Beginner Contest 383）
// URL: https://atcoder.jp/contests/abc383/tasks/abc383_f
// Memory Limit: 1024 MB
// Time Limit: 2500 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=510,INF=static_cast<ll>(5e18)+3;
ll N,Vol,K;
arr A[MAXN];
// color volume
ll dp[MAXN][50010]; // most utility
inline bool cmp(arr a,arr b){ // 按照颜色排序
return a[2]<b[2];
}
struct Things{
ll yen,u,c;
}T[MAXN];
pll Len[MAXN];
ll combDp[MAXN][50010];
ll colLim;
// memorized search
ll dfs(ll curCol,ll usedVol){
if(curCol>colLim) return 0;
if(usedVol>=Vol) return 0;
if(combDp[curCol][usedVol]!=-1) return combDp[curCol][usedVol];
ll res=0;
ROF(i,Vol-usedVol,0){
ll lres=0;
if(dp[curCol][i]==0){
lres=dfs(curCol+1,usedVol);
res=max(lres,res);
break;
}
lres=dp[curCol][i]+K;
lres+=dfs(curCol+1,usedVol+i);
res=max(lres,res);
}
combDp[curCol][usedVol]=res;
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>N>>Vol>>K;
// SumUtility+TdifferentColor*K
FOR(i, 1, N){ // yen Utility color
cin>>A[i][0]>>A[i][1]>>A[i][2];
}
sort(&A[1],&A[N+1],cmp);
ll idx=0;
T[1].yen=A[1][0],T[1].u=A[1][1],T[1].c=++idx;
FOR(i,2,N){
if(A[i-1][2]!=A[i][2]){ // 重新映射颜色
T[i].c=++idx;
}else{
T[i].c=idx;
}
T[i].yen=A[i][0],T[i].u=A[i][1];
}
Len[1].fi=1;
Len[idx].se=N;
FOR(i,2,N){
if(T[i].c!=T[i-1].c){
Len[T[i-1].c].se=i-1;
Len[T[i].c].fi=i;
}
}
// FOR(i,1,idx){
// cerr<<Len[i].fi<<' '<<Len[i].se<<'\n';
// }
// cerr<<T[3].yen<<' '<<T[3].c<<'\n';
FOR(i,1,idx){
FOR(j,Len[i].fi,Len[i].se){
ll yen=T[j].yen,val=T[j].u;
ROF(k,Vol,1){
if(k<yen) break;
dp[i][k]=max(dp[i][k],dp[i][k-yen]+val);
}
}
}
// FOR(i,1,idx){
// FOR(j,1,Vol){
// cerr<<dp[i][j]<<' ';
// }
// cerr<<'\n';
// }
colLim=idx;
FOR(i,0,idx){ // 初始化combDp
FOR(j,0,Vol){
combDp[i][j]=-1;
}
}
FOR(i,1,idx){
cerr<<dp[i][0]<<'\n';
}
cout<<dfs(1,0)<<'\n';
return 0;
}
/*
*/
```
用二分稍微优化了一点，多过了一些点
[http://atcoder.jp/contests/abc383/submissions/62387360](http://atcoder.jp/contests/abc383/submissions/62387360)
```cpp
// Problem: F - Diversity
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2024（AtCoder Beginner Contest 383）
// URL: https://atcoder.jp/contests/abc383/tasks/abc383_f
// Memory Limit: 1024 MB
// Time Limit: 2500 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=510,INF=static_cast<ll>(5e18)+3;
ll N,Vol,K;
arr A[MAXN];
// color volume
ll dp[MAXN][50010]; // most utility
inline bool cmp(arr a,arr b){ // 按照颜色排序
return a[2]<b[2];
}
struct Things{
ll yen,u,c;
}T[MAXN];
pll Len[MAXN];
ll combDp[MAXN][50010];
ll colLim;
// memorized search
ll dfs(ll curCol,ll usedVol){
if(curCol>colLim) return 0;
if(usedVol>=Vol) return 0;
if(combDp[curCol][usedVol]!=-1) return combDp[curCol][usedVol];
ll res=0;
res=dfs(curCol+1,usedVol); // 直接跳过该颜色
ll flag=1;
while(true){
ll idx=lower_bound(&dp[curCol][1],&dp[curCol][Vol-usedVol+1],flag)-&dp[curCol][0];
if(idx==Vol-usedVol+1) break;
ll lres=dp[curCol][idx]+K;
lres+=dfs(curCol+1,usedVol+idx);
res=max(res,lres);
flag=dp[curCol][idx+1]+1;
}
combDp[curCol][usedVol]=res;
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>N>>Vol>>K;
// SumUtility+TdifferentColor*K
FOR(i, 1, N){ // yen Utility color
cin>>A[i][0]>>A[i][1]>>A[i][2];
}
sort(&A[1],&A[N+1],cmp);
ll idx=0;
T[1].yen=A[1][0],T[1].u=A[1][1],T[1].c=++idx;
FOR(i,2,N){
if(A[i-1][2]!=A[i][2]){ // 重新映射颜色
T[i].c=++idx;
}else{
T[i].c=idx;
}
T[i].yen=A[i][0],T[i].u=A[i][1];
}
Len[1].fi=1;
Len[idx].se=N;
FOR(i,2,N){
if(T[i].c!=T[i-1].c){
Len[T[i-1].c].se=i-1;
Len[T[i].c].fi=i;
}
}
FOR(i,1,idx){
FOR(j,Len[i].fi,Len[i].se){
ll yen=T[j].yen,val=T[j].u;
ROF(k,Vol,1){
if(k<yen) break;
dp[i][k]=max(dp[i][k],dp[i][k-yen]+val);
}
}
}
colLim=idx;
FOR(i,0,idx){ // 初始化combDp
FOR(j,0,Vol){
combDp[i][j]=-1;
}
}
cout<<dfs(1,0)<<'\n';
return 0;
}
/*
*/
```
无法通过样例三
这个代码的问题在于dp[j-yen].c==0时，都会+K，
```cpp
FOR(i,1,N){ // 枚举物品
ll yen=T[i].yen,c=T[i].c,val=T[i].u; // 养成好习惯
ROF(j,Vol,1){
if(j<yen) break;
if(dp[j-yen].c<c){ // 这个代码的问题在于dp[j-yen].c==0
if(dp[j-yen].val+val+K>dp[j].val){
dp[j].val=dp[j-yen].val+val+K;
dp[j].c=c;
}
}else{
dp[j].val=max(dp[j-yen].val+val,dp[j].val);
}
// cerr<<j<<' '<<T[i].yen<<' '<<T[i].u<<' '<<T[i].c<<' '<<dp[j].val<<' '<<dp[j].c<<'\n';
}
}
```
```cpp
// Problem: F - Diversity
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2024（AtCoder Beginner Contest 383）
// URL: https://atcoder.jp/contests/abc383/tasks/abc383_f
// Memory Limit: 1024 MB
// Time Limit: 2500 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define debug(x) cerr<<x<<'\n'
#define CLR(i,a) memset(i,a,sizeof(i))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=510,INF=static_cast<ll>(5e18)+3;
ll N,Vol,K;
arr A[MAXN];
struct DP{
ll val,c;
};
// volume
DP dp[50010];
inline bool cmp(arr a,arr b){ // 按照颜色排序
return a[2]<b[2];
}
struct Things{
ll yen,u,c;
}T[MAXN];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>N>>Vol>>K;
// SumUtility+TdifferentColor*K
FOR(i, 1, N){ // yen Utility color
cin>>A[i][0]>>A[i][1]>>A[i][2];
}
sort(&A[1],&A[N+1],cmp);
// ll idx=0;
// T[1].yen=A[1][0],T[1].u=A[1][1],T[1].c=++idx;
// FOR(i,2,N){
// if(A[i-1][2]!=A[i][2]){ // 重新映射颜色
// T[i].c=++idx;
// }else{
// T[i].c=idx;
// }
// T[i].yen=A[i][0],T[i].u=A[i][1];
// }
CLR(dp,0);
// FOR(i,1,N){
// cerr<<A[i][0]<<' '<<A[i][1]<<' '<<A[i][2]<<'\n';
// }
FOR(i,1,N){ // 枚举物品
ll yen=A[i][0],c=A[i][2],val=A[i][1]; // 养成好习惯
ROF(j,Vol,1){
if(j<yen) break;
if(dp[j-yen].c<c){
if(dp[j-yen].val+val+K>dp[j].val){
dp[j].val=dp[j-yen].val+val+K;
dp[j].c=c;
}
}else{
if(dp[j-yen].val+val>dp[j].val){
dp[j].val=dp[j-yen].val+val;
dp[j].c=c;
}
}
// cerr<<j<<' '<<T[i].yen<<' '<<T[i].u<<' '<<T[i].c<<' '<<dp[j].val<<' '<<dp[j].c<<'\n';
}
}
FOR(i,0,Vol){
cerr<<i<<' '<<dp[i].val<<' '<<dp[i].c<<'\n';
}
cout<<dp[Vol].val<<'\n';
return 0;
}
/*
*/
```