20190810 替身使者——stand
思路：
对于$g(x)$,显然x最大是最优的
考虑用区间DP,设$f[l][r]$代表 l 到 r 区间内的g(x)的最大值
则状态转移方程为
$f[l][r]=\max_{j=l+1}^{j<r}f[l][j-1]+f[j+1][r]+g(peoplenum(j))$
但是发现 $l$ 与 $r$ 都在 $1e7$ 范围内,显然不行,所以要离散化
对于统计$people_num$,可以枚举在 $l$ 到 $r$ 中所有区间,用差分来统计即可
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
| #include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &F)
{
F = 0;
int R = 1;
char CH = getchar();
while(!isdigit(CH) && CH != '-') CH = getchar();
if(CH == '-') R = -1;
else F = (CH ^ 48);
CH = getchar();
while(isdigit(CH)) F = (F << 1) + (F << 3) + (CH ^ 48), CH = getchar();
F *= R;
}
long long f[1010][1010];
struct sz
{
int li, ri;
} ai[310];
int gx[6], ls[1010], num, n, m, ans;
bool vis[1010][1010];
long long sum(long long x)
{
return gx[1] * x + gx[2] * x * x + gx[3] * x * x * x + gx[4] * x * x * x * x + gx[5] * x * x * x * x * x;
}
long long Dp(int ll, int rr)
{
if(ll > rr) return 0;
if(vis[ll][rr]) return f[ll][rr];
vis[ll][rr] = 1;
int qi[rr - ll + 1] = {0};
for(int i = 1; i <= n; i++)
if(ai[i].li >= ll && ai[i].ri <= rr)
{
qi[ai[i].li - ll]++;
if(ai[i].ri < rr) qi[ai[i].ri - ll + 1]--;
}
long long ans = 0, pi = 0;
for(int i = 0; i < rr - ll + 1; i++)
{
pi += qi[i];
if(pi) ans = max(ans, Dp(ll, ll + i - 1) + Dp(ll + i + 1, rr) + sum(pi));
}
return f[ll][rr] = ans;
}
int main()
{
// freopen("stand.in", "r", stdin);
// freopen("stand.out", "w", stdout);
read(n), read(m);
for(int i = 1; i <= 5; i++) read(gx[i]);
for(int i = 1; i <= n; i++)
{
read(ai[i].li), read(ai[i].ri);
ls[++num] = ai[i].li, ls[++num] = ai[i].ri;
}
sort(ls + 1, ls + num + 1);
num = unique(ls + 1, ls + num + 1) - (ls + 1);
for(int i = 1; i <= n; i++)
{
ai[i].li = lower_bound(ls + 1, ls + num + 1, ai[i].li) - ls;
ai[i].ri = lower_bound(ls + 1, ls + num + 1, ai[i].ri) - ls;
}
cout << Dp(1, num) << endl;
return 0;
}
|