区间 $\text{Dp}$ 经典题。
题目描述
给定 $m$ 个三元组 $\{a_i,b_i,c_i\}$ ，表示第 $i$ 个人会选择区间 $[a_i,b_i]$ 中最便宜的值 $val_k$ 如果 $c_i \leq val_k$ 。设计一个长度为 $n$ 的数列 $val_i$ 使收益最大。
输出最大收益以及一种方案，含 $spj$ 。
样例：
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
| #1 in:
7 5
1 4 7
3 7 13
5 6 20
6 7 1
1 2 5
#1 out:
43
5 5 13 13 20 20 13
#2 in:
10 10
1 7 3141
2 8 5926
3 5 5358
1 9 9793
5 10 2384
4 7 6264
5 9 3383
9 10 27950
3 8 2884
1 7 1971
#2 out:
55021
1971 2384 5358 6264 6264 6264 6264 2384 27950 27950
|
数据范围：
$n \leq 50,m \leq 4000,1 \leq a_i \leq b_i \leq n,1 \leq c_i \leq 500000$
$subtask1:n=1$
$subtask2:n,m$
$subtask3:$无特殊限制
思路
首先，我们必须明白：$val_k \in T,T=\{c_1,c_2…c_m\},k \in [1,n]$ 。这需要一些简单的证明，这里不多赘述。
部分分
对于 $subtask1$ 而言，暴力枚举每一个价格，求出最大收益。期望得分： $30pt$
对于 $suntask2$ 而言，用 $O(2^m)$ 的时间暴力枚举每一个人是否会贡献答案。用线段树维护区间值，求出最大收益。时间复杂度 $O(2^m(n+m)\log n)$ ，期望得分： $60pt$ 。
这题确实良心
区间dp
首先离散化出有多少个不同的 $c_i$ ，用 $M$ 表示离散化之后的个数。我们设 $val_k$ 是区间 $[l,r]$ 之间的最小值。$(l \leq k \leq r)$ ，则对于任何一个 $l \leq a_i \leq b_i \leq r$ 的人而言，他的答案贡献必定是 $val_k$ 。那么我们用 $dp_{l,r,v}$ 表示区间 $[l,r]$ 内最小值为 $v$ 已得到的最优解。$cnt_k$ 表示有多少个人对该点的答案有贡献。则转移方程为：
$dp_{l,r,v}=\max\{dp_{l,r,v},dp_{l,k-1,v_1}+dp_{k+1,r,v_2}+cnt_k*v\}(v \leq v_1,v_2 \leq c_M)$
也许你会直呼：就这？
怎么可能！你算算复杂度：区间枚举 $O(n^3)$ 枚举价值 $O(m^3)$ 。加起来 $O(n^3m^3)$ 。过得了个寄！你说用四边形不等式优化到 $O(n^2m^3)$ ？开玩笑！？还不是过不了，何况这道题不能用四边形不等式优化。
优化
不能从 $n$ 入手，就优化 $m$ 。用一个数组 $g_{l,r,v}$ 预处理出 $\max\{dp_{l,r,v_1}\},v \leq v_1 \leq c_M$ 。直接优化成 $O(n^3m)$ 那过这道题就是氢氢忪忪了。
输出方案
记录每一种 $[l,r]$ 是从哪一个 $k$ 转移过来的即可。
AC 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
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
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define underMax(x,y) ((x)>(y)?(x):(y))
#define underMin(x,y) ((x)<(y)?(x):(y))
typedef long long ll;
using namespace std;
const int MAXN=51;
const int MAXM=4001;
template<class T>
inline void underRead(T &x)
{
x=0;
char ch=gh(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
if(t) x=-x;
}
int N,M,a[MAXM],b[MAXM],c[MAXM],cnt[MAXM],ans;
int dp[MAXN][MAXN][MAXM],g[MAXN][MAXN][MAXM];
vector<int>V;
inline void underInit(int l,int r,int k)
{
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=M;++i)
if(l<=a[i]&&b[i]<=r&&a[i]<=k&&k<=b[i]) ++cnt[c[i]];
}
int num[MAXN][MAXN][MAXM],renum[MAXN][MAXN][MAXM];
inline void underPrint(int l,int r,int k)
{
int id=num[l][r][k];
if(l<=id-1) underPrint(l,num[l][r][k]-1,renum[l][id-1][k]);
printf("%d ",V[k-1]);
if(id+1<=r) underPrint(id+1,r,renum[id+1][r][k]);
}
int main()
{
underRead(N),underRead(M);
for(int i=1;i<=M;++i)
{
underRead(a[i]),underRead(b[i]),underRead(c[i]);
V.push_back(c[i]);
}
sort(V.begin(),V.end());
V.erase(unique(V.begin(),V.end()),V.end());
for(int i=1;i<=M;++i) c[i]=lower_bound(V.begin(),V.end(),c[i])-V.begin()+1;
for(int l=N;l>=1;--l)
for(int r=l;r<=N;++r)
{
for(int k=l,sum;k<=r;++k)
{
underInit(l,r,k);
sum=0;
for(int i=V.size();i>=1;--i)
{
sum+=cnt[i];
ans=sum*V[i-1]+g[l][k-1][i]+g[k+1][r][i];
if(ans>dp[l][r][i]||!dp[l][r][i])
{
dp[l][r][i]=ans;
num[l][r][i]=k;
}
}
}
for(int k=V.size();k>=1;--k)
{
if(dp[l][r][k]>g[l][r][k+1]||!g[l][r][k+1])
{
g[l][r][k]=dp[l][r][k];
renum[l][r][k]=k;
}
else
{
g[l][r][k]=g[l][r][k+1];
renum[l][r][k]=renum[l][r][k+1];
}
}
}
printf("%d\n",g[1][N][1]);
underPrint(1,N,renum[1][N][1]);
cerr<<endl<<"time:"<<clock()<<"ms"<<endl;
return 0;
}
|