Znzryb's Blog
0%

Posted on Edited on

思路讲解

https://www.luogu.com/article/wa8c5zfe 还有一种差分想法，更加简洁，挺好的

10就是在差分数组中有一个-1，01就是差分数组中有一个1，把差分数组加起来，就能得到01数量-10数量的值，然后根据差分的结论，我们就知道差分总值只和首项和末项有关。

首先根据上题，我们需要发现两个结论：
1） 首尾相同的字符串一定是平衡的。
2） 首尾不相同的字符串一定是不平衡的。

这是为什么那？

直接证明这个结论比较难，可以这么想，大家可以想象一个都是0序列，将里面的0变为1（通过这一操作可以生成任何序列）会对10，01数量造成什么变化那？（其实我也不是很会证明，大家就随便看看吧）

image

我们发现，只有在对空情况的操作时，才会产生不平衡这样的问题

而且对空情况的左右两种镜像情况分别为一组，这两组中的任意两对都是互相抵消的（比如10++ && 01++ 就会使数列平衡）

那么其实就完成了，头尾都是0的情况嘛所有操作都使数列保持平衡，头尾都是1的情况对空操作也就抵消了，那么就得到了上述的结论。

有了这个结论以后剩下的就简单了，剩下的就看代码吧，关键地方有注释，然后注意特判只有单个字母的情况。

AC代码

AC

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75411197

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
// Problem: Tokitsukaze and Balance String (hard)
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95336/C
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// by znzryb
// 
// 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
#define pb push_back

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;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3,mod=static_cast<ll>(1e9)+7;

ll N,T;
char S[MAXN];//Sd[MAXN];
ull ans=0,pow2[MAXN];

inline void solve(){
	cin>>N;
	ans=0;
	ll cnt=0;
	FOR(i, 1, N){
		cin>>S[i];
		if(S[i]=='?') ++cnt;
		// Sd[i]=S[i];
	}
	if(N==1){
		if(S[1]!='?') cout<<1<<'\n';
		else cout<<2<<'\n';
		return;
	}
	if(S[1]=='?' && S[N]=='?'){
		ans+=2*pow2[cnt-2]*(N-2);	// ?为0，0 1，1的情况
		//cerr<<ans<<'\n';
		ans%=mod;
		ans+=4*pow2[cnt-2];	// ?,? 1,0 0,1的情况(两种情况，每种情况有两种位置，所以*4)
		//cerr<<ans<<'\n';
		ans%=mod;
	}else if(S[1]=='?' || S[N]=='?'){
		ans+=pow2[cnt-1]*(N-2);
		ans%=mod;
		ans+=2*pow2[cnt-1];
		ans%=mod;
	}else{
		if(S[1]!=S[N]){
			ans=2*pow2[cnt];
			ans%=mod;
		}else{
			ans=pow2[cnt]*(N-2);
			ans%=mod;
		}
	}
	cout<<ans%mod<<'\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	pow2[0]=1;
	FOR(i,1,MAXN-5){
		pow2[i]=(pow2[i-1]*2)%mod;
	}
	while(T--){
		solve();
	}
	return 0;
}
/*
AC

*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

如同这个例子一样，已经匹配好的我们就可以不管了，因为是两两匹配的，所以说回文串中心不会改变，不用担心会有什么问题

image

然后最容易想不通的就是长串内部的消除问题

image

1
2
3
4
5
6
7
8
FOR(i,0,25){
	if(cnta[i]>=cntb[i]) cnta[i]-=cntb[i];
	else shortRem+=cntb[i]-cnta[i],cntb[i]-=cnta[i],cnta[i]=0;
}
ll longRem=0;
FOR(i,0,25){
	if(cnta[i]%2==1) ++longRem;
}

abgfhh 和abcdeee的匹配过程（longRem ≥ shortRem 就可以像下图这样将重复元素加入到对称轴两边，进而就可以抵消）

image

当（longRem < shortRem），为什么答案就是shortRem那？

说白了其实就是把这些奇数的都给搞定了，剩下的就都是偶数的，就比较好搞了（）

image

与longRem匹配完剩余是偶数的情况更简单，就不画了。

AC代码

AC

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75405249

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// Problem: Tokitsukaze and Concatenate‌ Palindrome
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95336/D
// Memory Limit: 512 MB
// Time Limit: 4000 ms
// by znzryb
// 
// 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
#define pb push_back

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;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T;
char Ao[MAXN],Bo[MAXN],A[MAXN],B[MAXN];
ll cnta[29],cntb[29];

inline void solve(){
	cin>>N>>M;
	FOR(i,1,N){
		cin>>A[i];
	}
	FOR(i,1,M){
		cin>>B[i];
	}
	FOR(i,0,27){
		cnta[i]=0;
		cntb[i]=0;
	}
	if(N<M){
		FOR(i,1,M){
			swap(A[i],B[i]);
		}
		swap(N,M);
	}
	FOR(i,1,N){
		cnta[A[i]-'a']+=1;
	}
	FOR(i,1,M){
		cntb[B[i]-'a']+=1;
	}
	ll shortRem=0;
	FOR(i,0,25){
		if(cnta[i]>=cntb[i]) cnta[i]-=cntb[i];
		else shortRem+=cntb[i]-cnta[i],cntb[i]-=cnta[i],cnta[i]=0;
	}
	ll longRem=0;
	FOR(i,0,25){
		if(cnta[i]%2==1) ++longRem;
	}
	if(shortRem>longRem){
		cout<<shortRem<<'\n';
	}else{
		// if((N+M)%2!=0) longRem= longRem==0?0:longRem-1;
		cout<<shortRem+(longRem-shortRem)/2<<'\n';
	}
	
	// FOR(i,1,N){
		// cerr<<A[i]<<' ';
	// }
	// cerr<<'\n';
	// FOR(i,1,M){
		// cerr<<B[i]<<' ';
	// }
	// cerr<<'\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}
/*

*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

1
2
3
4
5
6
struct cmp{
	bool operator()(const pll &a,const pll &b) const {
		return a.fi>b.fi;
	}
};
multiset<pll,cmp> B;

给multiset的cmp记得加const，否则有可能CE

1
2
3
4
5
6
7
8
9
for(multiset<pll>::iterator it=B.begin();it!=B.end();){
	if(it->first<A[i]){
		break;
	}
	multiset<pll>::iterator next_it=next(it);
	ans[it->second]=i;
	B.erase(it);
	it=next_it;
}

然后erase（）只能传入iterator，不能够传入reverse_iterator

AC代码

https://atcoder.jp/contests/abc382/submissions/62419496

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// Problem: C - Kaiten Sushi
// Contest: AtCoder - AtCoder Beginner Contest 382
// URL: https://atcoder.jp/contests/abc382/tasks/abc382_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// 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
#define pb push_back

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=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,A[MAXN];
// pll B[MAXN];
struct cmp{
	bool operator()(const pll &a,const pll &b) const {
		return a.fi>b.fi;
	}
};
multiset<pll,cmp> B;
ll ans[MAXN];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>M;
	FOR(i, 1, N){
		cin>>A[i];
	}
	FOR(i, 1, M){
		ll b;
		cin>>b;
		B.insert({b,i});
	}
	FOR(i,1,M){
		ans[i]=-1;
	}
	
	FOR(i,1,N){
		for(multiset<pll>::iterator it=B.begin();it!=B.end();){
			if(it->first<A[i]){
				break;
			}
			multiset<pll>::iterator next_it=next(it);
			ans[it->second]=i;
			B.erase(it);
			it=next_it;
		}
	}
	FOR(i,1,M){
		cout<<ans[i]<<'\n';
	}
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc382/submissions/62419496
*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

ABC- 371 - E- I Hate Sigma Problems

【AtCoder 初学者竞赛 390比赛讲解】 【精准空降到 1:05:10】 https://www.bilibili.com/video/BV1NNfkY2Esv/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=3910

正过来求贡献的想法

image

这个左端点选择数和右端点选择数怎么样快速求出？

还是一样的，用类似于邻接表的数据结构二分快速求出

AC代码

AC（这个代码稍微有点啰嗦）

https://atcoder.jp/contests/abc390/submissions/62410948

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
// Problem: F - Double Sum 3
// Contest: AtCoder - AtCoder Beginner Contest 390
// URL: https://atcoder.jp/contests/abc390/tasks/abc390_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// 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
#define pb push_back

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=static_cast<ll>(3e5)+10,INF=static_cast<ll>(5e18)+3;

ll N,A[MAXN];
// ull diffSum[MAXN];// arithmetic sequence
// ll diff[MAXN],origin[MAXN]; 
vector<ll> g[MAXN];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N;
	FOR(i, 1, N){
		cin>>A[i];
		g[A[i]].pb(i);
	}
	ull ans=0;
	FOR(i,1,N){	// 二分算贡献
		ll lres=1,rres=N;
		FOR(j,A[i]-1,A[i]-1){
			if(g[j].empty()) continue;
			auto it=upper_bound(all(g[j]),i);
			if(it==g[j].end()) continue;
			rres=min(*it-1,rres);
		}
		
		FOR(j,A[i]-1,A[i]){
			if(j==A[i]){
				auto it=lower_bound(all(g[j]),i);
				if(it==g[j].begin()) continue;	// 找不到就说明无限制
				it--;
				lres=max(lres,*it+1);
			}else{
				if(g[j].empty()) continue;
				auto it=lower_bound(all(g[j]),i);
				if(it==g[j].begin()) continue;	// 找不到就说明无限制
				it--;
				lres=max(lres,*it+1);
			}
			
		}
		cerr<<i<<' '<<lres<<' '<<rres<<'\n';
		ans+=(i-lres+1)*(rres-i+1);
	}
	
	cout<<ans<<'\n';
	
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc390/submissions/62410948
*/

心路历程（WA，TLE，MLE……）

思路排除，不太可能是线段树

ABC-391-E - Hierarchical Majority Vote（三叉线段树） 这种合并比较容易的更适合用线段树解决

image

反过来贡献的想法（有缺陷）

image

1，3，6，10的由来（1，2，3，4代表所有以他们为结尾的区间）

image

像这种问题，考虑区间合并比较麻烦，不如化整为零，计算个体的贡献，对所有位于它贡献位置后面的全部减id（之所以是减下标id是因为所有它后面的位置所代表的区间中有id个含有这个位置的区间）

image

好，现在知道了知道了贡献我们怎么求解这个问题。那么问题来了，我们怎么做到O（n）的求贡献那？

image

我们发现题目贴心的有了这么一个限制条件，我们可以快捷的用二分求出贡献为止，利用类似于邻接表的数据结构。

程序过不了样例2

image

原因是在于以下（3，1已经被考虑没用了，但是4在有3的情况下也没用这点没考虑）

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// Problem: F - Double Sum 3
// Contest: AtCoder - AtCoder Beginner Contest 390
// URL: https://atcoder.jp/contests/abc390/tasks/abc390_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// 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
#define pb push_back

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=static_cast<ll>(3e5)+10,INF=static_cast<ll>(5e18)+3;

ll N,A[MAXN];
ull diffSum[MAXN];// arithmetic sequence
ll diff[MAXN],origin[MAXN]; 
vector<ll> g[MAXN];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N;
	FOR(i, 1, N){
		cin>>A[i];
		diffSum[i]=diffSum[i-1]+i;	// 形成的是等差数列1，2，3，。。。的前缀和
		g[A[i]].pb(i);
	}
	FOR(i,1,N){	// 二分算贡献
		ll res=MAXN,reduce=0;
		FOR(j,A[i]-1,A[i]+1){
			if(g[j].empty()) continue;
			auto it=upper_bound(all(g[j]),i);
			if(it==g[j].end()) continue;
			res=min(*it,res);
		}
		if(res==MAXN) continue;
		diff[res]-=i+reduce;
	}
	FOR(i,1,N){
		origin[i]=origin[i-1]+diff[i];
	}
	ull ans=0;
	FOR(i,1,N){
		ans+=diffSum[i]+origin[i];
	}
	cout<<ans<<'\n';
	
	FOR(i,1,N){
		cerr<<origin[i]<<'\n';
	}
	FOR(i,1,N){
		cerr<<diff[i]<<' ';
	}
	cerr<<'\n';
	return 0;
}
/*

*/

Posted on Edited on

思路讲解

ABC-390-E - Vitamin Balance

我感觉很像这道题，因为我就只要背包分成几块就好了

但是又有点问题，合起来的过程需要枚举非常多次，那道题只要合并3个背包就好了，我们要合并500个背包，想想就TLE

所以这种问题一般就别想裸的背包合并，需要使用类似于向斜下方走的dp

image

比较简单的来讲，类似于CF-994-D. Shift + Esc （多变量优化dp）

需要关注一下颜色之间的转移以及最优状态

image

1
2
3
4
5
6
7
8
9
10
11
12
13
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
// 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) 生成的，空间乘以这个循环次数自然就是时间复杂度了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
// 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
// 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，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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';
		
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
// 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;
}
/*

*/