BZOJ 4380 Myjnie

发表于 | 更新于

Link

设计出了状态，但没有想到转移

Solution

f[l][r][c]f[l][r][c]表示在洗车店区间[l,r][l,r]，最便宜的价格为cc的最大收入。 一开始想转移的时候，觉得应该是所有经过一段区间的消费者都要算进去，但这样就会有重复 最后发现自己的想法是多么naive 每次转移f[l][r][c]f[l][r][c]，只算被区间完全包含的消费者们。 对于枚举到的每个区间，处理h[i][c]h[i][c]，表示经过点ii而且要求高于cc的消费者的个数，然后就枚举断点转移就好了。

Code

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
#include "lucida"

using std::max;
using std::sort;
using std::lower_bound;
using std::unique;
using std::partial_sum;
const int MAXN=50+11,MAXM=4000+11;
int a[MAXN],f[MAXN][MAXN][MAXM],g[MAXN][MAXN][MAXM],pp[MAXN][MAXN][MAXM],plim[MAXN][MAXN][MAXM];
void DFS(int l,int r,int c) {
	if(l>r || !pp[l][r][c]) 
		return;
	a[pp[l][r][c]]=plim[l][r][c];
	DFS(l,pp[l][r][c]-1,plim[l][r][c]);
	DFS(pp[l][r][c]+1,r,plim[l][r][c]);
}
int main() {
//	freopen("input","r",stdin);
	static int lbd[MAXM],rbd[MAXM],lim[MAXM],nums[MAXM],cnt[MAXN][MAXM];
	int n,m;is>>n>>m;
	for(int i=1;i<=m;++i) {
		is>>lbd[i]>>rbd[i]>>lim[i];
		nums[i]=lim[i];
	}
	sort(nums+1,nums+1+m);
	int nc=unique(nums+1,nums+1+m)-nums-1;
	for(int i=1;i<=m;++i)
		lim[i]=lower_bound(nums+1,nums+1+nc,lim[i])-nums;
	//处理出被当前区间完全包含的
	//最低要求为c的
	//经过i点的
	//数目h[i][c]
	for(int length=1;length<=n;++length)
		for(int l=1,r=length;r<=n;++l,++r) {
			memset(cnt,0,sizeof(cnt));
			for(int i=1;i<=m;++i) 
				if(l<=lbd[i] && rbd[i]<=r){
					for(int p=lbd[i];p<=rbd[i];++p)
						cnt[p][lim[i]]++;
				}
			for(int i=1;i<=n;++i) 
				//partial_sum(cnt[i]+1,cnt[i]+1+m,cnt[i]+1);
				for(int c=m-1;c;--c)
					cnt[i][c]+=cnt[i][c+1];
			for(int c=1;c<=m;++c)
				for(int i=l;i<=r;++i)
					if(chkmx(f[l][r][c],g[l][i-1][c]+g[i+1][r][c]+cnt[i][c]*nums[c])) {
						pp[l][r][c]=i;
						plim[l][r][c]=c;
						g[l][r][c]=f[l][r][c];
					}
			for(int c=m-1;c;--c)
				if(chkmx(g[l][r][c],g[l][r][c+1])) {
					pp[l][r][c]=pp[l][r][c+1];
					plim[l][r][c]=plim[l][r][c+1];
				}
		}
	os<<g[1][n][1]<<'\n';
	DFS(1,n,1);
	for(int i=1;i<=n;++i)
		os<<nums[a[i]?a[i]:m]<<(i==n?'\n':' ');
	return 0;
}