http://codeforces.com/problemset/problem/834/D
将一个长度为n的序列分为k段
使得总价值最大一段区间的价值表示为区间内不同数字的个数
n<=35000,k<=50
这题的dp是十分显然的,用dp[i][j]表示前i个数字分成j段的最大值
状态转移方程就是 dp[i][j] = max(dp[i - 1][k] + dis[k + 1][j] | (0 <= k <= j - 1))
但是乍一想可能是个O(knn)的算法,仔细一想果然是。
考虑线段树的优化。显然根据状态转移方程,线段树维护的是dp[i - 1][k] + dis[k + 1][j]的最大值
也就是对每一层都build一次线段树,然后以此查询更新,时间复杂度是O(knlnn),看着十分科学
其中一个难点在于对颜色种类的维护,dis这个35k * 35k的数组肯定是存不下的,仔细一想其实不需要什么花里胡哨的操作,用一个pre数组存储上一个这个颜色出现的地方,当遇到这个颜色的时候,在线段树pre[x] + 1,x的位置全部加上1,意在pre[x] + 1到x出现了这个颜色,种类++;
然后整个思路就出来了,对于每一层状态,用一个build更新上一层的dp[i - 1][k],dis在查询的过程中动态更新,这种听起来就很像正解的做法一般就是正解。
复制代码
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155#include <map> #include <set> #include <cmath> #include <queue> #include <stack> #include <vector> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <functional> using namespace std; const int MAXBUF=10000;char buf[MAXBUF],*ps=buf,*pe=buf+1; inline bool isdigit(const char& n) {return (n>='0'&&n<='9');} inline void rnext(){if(++ps==pe)pe=(ps=buf)+fread(buf,sizeof(char),sizeof(buf)/sizeof(char),stdin);} template <class T> inline bool in(T &ans){ #ifdef VSCode ans=0;T f=1;register char c; do{c=getchar();if ('-'==c)f=-1;}while(!isdigit(c)&&c!=EOF); if(c==EOF)return false;do{ans=(ans<<1)+(ans<<3)+c-48; c=getchar();}while(isdigit(c)&&c!=EOF);ans*=f;return true; #endif #ifndef VSCode ans =0;T f=1;if(ps==pe)return false;do{rnext();if('-'==*ps)f=-1;} while(!isdigit(*ps)&&ps!=pe);if(ps==pe)return false;do{ans=(ans<<1)+(ans<<3)+*ps-48; rnext();}while(isdigit(*ps)&&ps!=pe);ans*=f;return true; #endif }const int MAXOUT=10000; char bufout[MAXOUT], outtmp[50],*pout = bufout, *pend = bufout+MAXOUT; inline void write(){fwrite(bufout,sizeof(char),pout-bufout,stdout);pout = bufout;} inline void out_char(char c){*(pout++)=c;if(pout==pend)write();} inline void out_str(char *s){while(*s){*(pout++)=*(s++);if(pout==pend)write();}} template <class T>inline void out_int(T x) {if(!x){out_char('0');return;} if(x<0)x=-x,out_char('-');int len=0;while(x){outtmp[len++]=x%10+48;x/=10;}outtmp[len]=0; for(int i=0,j=len-1;i<j;i++,j--) swap(outtmp[i],outtmp[j]);out_str(outtmp);} template<typename T, typename... T2> inline int in(T& value, T2&... value2) { in(value); return in(value2...); } #define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--) #define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x) #define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%dn", x) #define Prl(x) printf("%lldn",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear(); #define LL long long #define ULL unsigned long long #define mp make_pair #define PII pair<int,int> #define PIL pair<int,long long> #define PLL pair<long long,long long> #define pb push_back #define fi first #define se second #define Vec Point typedef vector<int> VI; const double eps = 1e-9; const int maxn = 35010; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int N,M,tmp,K; int a[maxn]; int dp[maxn][55]; //以这个结尾 int pre[maxn]; int display[maxn]; struct Tree{ int l,r; int MAX,lazy; }tree[maxn * 4]; void Pushdown(int t){ if(tree[t].lazy){ tree[t << 1].lazy += tree[t].lazy; tree[t << 1].MAX += tree[t].lazy; tree[t << 1 | 1].lazy += tree[t].lazy; tree[t << 1 | 1].MAX += tree[t].lazy; tree[t].lazy = 0; } } void Pushup(int t){ tree[t].MAX = max(tree[t << 1].MAX,tree[t << 1 | 1].MAX); } void Build(int t,int l,int r,int flag){ tree[t].l = l; tree[t].r = r; tree[t].lazy = 0; if(l == r){ tree[t].MAX = dp[l - 1][flag]; return; } int m = (l + r) >> 1; Build(t << 1,l,m,flag); Build(t << 1 | 1,m + 1,r,flag); Pushup(t); } void update(int t,int l,int r){ if(l <= tree[t].l && tree[t].r <= r){ tree[t].MAX++; tree[t].lazy++; return; } Pushdown(t); int m = (tree[t].l + tree[t].r) >> 1; if(r <= m) update(t << 1,l,r); else if(l > m) update(t << 1 | 1,l,r); else{ update(t << 1,l,m); update(t << 1 | 1,m + 1,r); } Pushup(t); } int query(int t,int l,int r){ if(l <= tree[t].l && tree[t].r <= r){ return tree[t].MAX; } Pushdown(t); int m = (tree[t].l + tree[t].r) >> 1; if(r <= m){ return query(t << 1,l,r); }else if(l > m){ return query(t << 1 | 1,l,r); }else{ return max(query(t << 1 | 1,m + 1,r),query(t << 1,l,m)); } } int main() { in(N,K); For(i,1,N) display[i] = 0; For(i,1,N){ in(a[i]); pre[i] = display[a[i]]; display[a[i]] = i; } For(i,1,K){ //dp[i][j] = max(dp[i - 1][k] + dis[k + 1][j]) (0 <= k <= j - 1)); Build(1,1,N,i - 1); For(j,1,N){ update(1,pre[j] + 1,j); dp[j][i] = query(1,1,j); // cout << dp[j][i] << " "; } // cout << endl; } Pri(dp[N][K]); #ifdef VSCode write(); system("pause"); #endif return 0; }
转载于:https://www.cnblogs.com/Hugh-Locke/p/9499724.html
最后
以上就是乐观马里奥最近收集整理的关于CodeForces834D DP + 线段树的全部内容,更多相关CodeForces834D内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复