2016 UESTC Training for Dynamic Programming
A - 柱爷与咸鱼神功
题意：
柱爷有n(<=5000)点心情去学m(<=5000)个招式,每个招式会得到一定的修炼值,但要消耗一定的心情,求最多的修炼值。
题解：
0.这是一个裸的背包问题，用每一个物品去更新每一种背包的状态.
1.状态定义:dp[i]表示用i点心情得到的最多修炼值。
2.状态转移:dp[i] = max{dp[i-v[j]]+w[j]}
代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <cstdio>#include <algorithm>#include <iostream>#include <cstring>using namespace std;const int N = 100010;int n,m,v[N],w[N],dp[N];int main(){ scanf("%d%d",&n,&m); for(int i = 1;i <= m;++i){ scanf("%d%d",&v[i],&w[i]); } for(int i = 1;i <= m;++i){ for(int j = n;j >= v[i];--j) dp[j] = max(dp[j-v[i]]+w[i],dp[j]); } cout<<dp[n]<<endl; return 0;}//- xgtao - |
B - 柱爷与最大区间和
题意：
给出一个长度为n(<=500000)的序列,输出两个不相邻区间的和。
题解：
0.因为要严格控制不相邻的区间,定义状态f[i][0/1]表示在1~i之前的最大区间和(并且不选或选第i点),g[i][0/1]表示在i~n之前的最大区间和(并且不选或选i点)。
1.f[i][0] = max{f[i-1][0],f[i-1][1]} f[i][1] = max{f[i-1][1]+w[i],w[i]} g[i][0] = max{g[i+1][0],g[i+1][1]} g[i][1] = max{g[i+1][1]+w[i],w[i]}
2.最后的答案即为max{f[i][0]+g[i][0],f[i][0]+g[i][1],f[i][1]+g[i][0]}
代码：
|
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
|
#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int inf = 1<<30;const int N = 500010;int f[N][2],g[N][2],a[N],n,ans = -inf;int main(){ scanf("%d",&n); for(int i = 1;i <= n;++i)scanf("%d",&a[i]); f[0][0] = f[0][1] = -inf,g[n+1][0] = g[n+1][1] = -inf; for(int i = 1;i <= n;++i){ f[i][1] = max(f[i-1][1]+a[i],a[i]); f[i][0] = max(f[i-1][1],f[i-1][0]); } for(int i = n;i >= 1;--i){ g[i][1] = max(g[i+1][1]+a[i],a[i]); g[i][0] = max(g[i+1][1],g[i+1][0]); } for(int i = 1;i <= n;++i){ int ret = max(max(f[i][0]+g[i+1][1],f[i][0]+g[i][0]),f[i][1]+g[i+1][0]); ans = max(ans,ret); } cout<<ans<<endl; return 0;}//- xgtao - |
C - 柱爷的下凡
题意：
用三种硬币表示1~n(<=200)的数,并且总共用的硬币数最少,多组数据(<=200)！！！！！
题解：
0.三种硬币中必定包含一枚1元。
1.那么另外两种硬币b,c就可以枚举,定义状态dp[i]表示表示出i元花费最少的硬币数。
2.状态转移即为:dp[i] = max{dp[i-b]+1,dp[i-c]+1,dp[i-1]+1},只需要计算Σdp[1~n]即可。
3.这是O(n^3)的算法,但是有多组数据就是O(n^4)。
4.我们可以通过打表解决,枚举n,预处理出所有n的情况,再用O(1)查询。
代码：
|
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
|
#include <cstdio>#include <iostream>#include <algorithm>using namespace std;const int N = 500;int T,n,dp[N],a = 1,ans2[N],ans3[N],ans = 1e9,ret;int main(){ freopen("C_list.cpp","w",stdout); ans2[1] = 2,ans3[1] = 3; ans2[2] = 2,ans3[2] = 3; ans2[3] = 2,ans3[3] = 3; for(int i = 4;i <= 200;++i){ ans = 1e9; for(int j = 2;j < i;++j){ for(int k = j+1;k <= i;++k){ ret = 0; dp[0] = 0; for(int c = 1;c <= i;++c){ if(c >= k)dp[c] = min(dp[c-k],min(dp[c-j],dp[c-1]))+1; else if(c >= j)dp[c] = min(dp[c-j],dp[c-1])+1; else if(c >= 1)dp[c] = dp[c-1]+1; } for(int c = 1;c <= i;++c)ret += dp[c]; if(ret < ans)ans = ret,ans2[i] = j,ans3[i] = k; } } } for(int i = 1;i <= 200;++i){ printf(" if(n == %d)printf",i); printf("("1 %d %d\n");
",ans2[i],ans3[i]); } return 0;} |
|
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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
|
#include <cstdio>int T,n;int main(){ scanf("%d",&T); while(T--){ scanf("%d",&n); if(n == 1)printf("1 2 3
"); if(n == 2)printf("1 2 3
"); if(n == 3)printf("1 2 3
"); if(n == 4)printf("1 2 3
"); if(n == 5)printf("1 2 3
"); if(n == 6)printf("1 2 3
"); if(n == 7)printf("1 2 5
"); if(n == 8)printf("1 3 4
"); if(n == 9)printf("1 3 4
"); if(n == 10)printf("1 2 5
"); if(n == 11)printf("1 2 5
"); if(n == 12)printf("1 4 6
"); if(n == 13)printf("1 4 6
"); if(n == 14)printf("1 4 6
"); if(n == 15)printf("1 3 7
"); if(n == 16)printf("1 4 6
"); if(n == 17)printf("1 3 7
"); if(n == 18)printf("1 4 6
"); if(n == 19)printf("1 3 8
"); if(n == 20)printf("1 3 8
"); if(n == 21)printf("1 5 7
"); if(n == 22)printf("1 4 9
"); if(n == 23)printf("1 4 9
"); if(n == 24)printf("1 5 8
"); if(n == 25)printf("1 5 8
"); if(n == 26)printf("1 5 8
"); if(n == 27)printf("1 5 8
"); if(n == 28)printf("1 4 9
"); if(n == 29)printf("1 5 8
"); if(n == 30)printf("1 5 8
"); if(n == 31)printf("1 4 9
"); if(n == 32)printf("1 5 8
"); if(n == 33)printf("1 5 8
"); if(n == 34)printf("1 7 11
"); if(n == 35)printf("1 7 11
"); if(n == 36)printf("1 7 11
"); if(n == 37)printf("1 5 12
"); if(n == 38)printf("1 5 12
"); if(n == 39)printf("1 5 12
"); if(n == 40)printf("1 7 11
"); if(n == 41)printf("1 5 12
"); if(n == 42)printf("1 5 12
"); if(n == 43)printf("1 5 12
"); if(n == 44)printf("1 7 11
"); if(n == 45)printf("1 7 11
"); if(n == 46)printf("1 7 11
"); if(n == 47)printf("1 7 11
"); if(n == 48)printf("1 6 14
"); if(n == 49)printf("1 6 14
"); if(n == 50)printf("1 6 14
"); if(n == 51)printf("1 6 14
"); if(n == 52)printf("1 8 13
"); if(n == 53)printf("1 8 13
"); if(n == 54)printf("1 8 13
"); if(n == 55)printf("1 8 13
"); if(n == 56)printf("1 8 13
"); if(n == 57)printf("1 6 14
"); if(n == 58)printf("1 6 14
"); if(n == 59)printf("1 6 14
"); if(n == 60)printf("1 8 13
"); if(n == 61)printf("1 8 13
"); if(n == 62)printf("1 6 14
"); if(n == 63)printf("1 6 14
"); if(n == 64)printf("1 6 14
"); if(n == 65)printf("1 8 13
"); if(n == 66)printf("1 8 13
"); if(n == 67)printf("1 8 13
"); if(n == 68)printf("1 8 13
"); if(n == 69)printf("1 7 17
"); if(n == 70)printf("1 7 17
"); if(n == 71)printf("1 7 17
"); if(n == 72)printf("1 7 17
"); if(n == 73)printf("1 7 17
"); if(n == 74)printf("1 9 14
"); if(n == 75)printf("1 7 17
"); if(n == 76)printf("1 7 17
"); if(n == 77)printf("1 7 17
"); if(n == 78)printf("1 7 17
"); if(n == 79)printf("1 7 17
"); if(n == 80)printf("1 10 16
"); if(n == 81)printf("1 10 16
"); if(n == 82)printf("1 10 16
"); if(n == 83)printf("1 10 16
"); if(n == 84)printf("1 8 19
"); if(n == 85)printf("1 8 19
"); if(n == 86)printf("1 8 19
"); if(n == 87)printf("1 8 19
"); if(n == 88)printf("1 6 20
"); if(n == 89)printf("1 10 17
"); if(n == 90)printf("1 11 15
"); if(n == 91)printf("1 11 15
"); if(n == 92)printf("1 11 15
"); if(n == 93)printf("1 11 15
"); if(n == 94)printf("1 11 18
"); if(n == 95)printf("1 11 18
"); if(n == 96)printf("1 12 19
"); if(n == 97)printf("1 12 19
"); if(n == 98)printf("1 12 19
"); if(n == 99)printf("1 12 19
"); if(n == 100)printf("1 12 19
"); if(n == 101)printf("1 12 19
"); if(n == 102)printf("1 12 19
"); if(n == 103)printf("1 12 19
"); if(n == 104)printf("1 12 19
"); if(n == 105)printf("1 12 19
"); if(n == 106)printf("1 12 19
"); if(n == 107)printf("1 12 19
"); if(n == 108)printf("1 12 19
"); if(n == 109)printf("1 12 19
"); if(n == 110)printf("1 12 19
"); if(n == 111)printf("1 13 18
"); if(n == 112)printf("1 12 19
"); if(n == 113)printf("1 12 19
"); if(n == 114)printf("1 12 19
"); if(n == 115)printf("1 12 19
"); if(n == 116)printf("1 12 19
"); if(n == 117)printf("1 12 19
"); if(n == 118)printf("1 12 19
"); if(n == 119)printf("1 12 19
"); if(n == 120)printf("1 12 19
"); if(n == 121)printf("1 12 19
"); if(n == 122)printf("1 12 19
"); if(n == 123)printf("1 7 23
"); if(n == 124)printf("1 7 23
"); if(n == 125)printf("1 8 27
"); if(n == 126)printf("1 8 27
"); if(n == 127)printf("1 8 27
"); if(n == 128)printf("1 9 23
"); if(n == 129)printf("1 9 23
"); if(n == 130)printf("1 9 23
"); if(n == 131)printf("1 9 30
"); if(n == 132)printf("1 9 30
"); if(n == 133)printf("1 14 22
"); if(n == 134)printf("1 14 22
"); if(n == 135)printf("1 10 26
"); if(n == 136)printf("1 14 22
"); if(n == 137)printf("1 8 27
"); if(n == 138)printf("1 8 27
"); if(n == 139)printf("1 14 22
"); if(n == 140)printf("1 8 27
"); if(n == 141)printf("1 8 27
"); if(n == 142)printf("1 10 26
"); if(n == 143)printf("1 8 27
"); if(n == 144)printf("1 8 27
"); if(n == 145)printf("1 8 27
"); if(n == 146)printf("1 8 27
"); if(n == 147)printf("1 8 27
"); if(n == 148)printf("1 8 27
"); if(n == 149)printf("1 8 27
"); if(n == 150)printf("1 8 27
"); if(n == 151)printf("1 8 27
"); if(n == 152)printf("1 8 27
"); if(n == 153)printf("1 9 30
"); if(n == 154)printf("1 9 30
"); if(n == 155)printf("1 9 30
"); if(n == 156)printf("1 9 30
"); if(n == 157)printf("1 9 30
"); if(n == 158)printf("1 9 30
"); if(n == 159)printf("1 9 30
"); if(n == 160)printf("1 9 30
"); if(n == 161)printf("1 9 30
"); if(n == 162)printf("1 9 30
"); if(n == 163)printf("1 9 30
"); if(n == 164)printf("1 9 30
"); if(n == 165)printf("1 9 30
"); if(n == 166)printf("1 9 30
"); if(n == 167)printf("1 9 30
"); if(n == 168)printf("1 9 30
"); if(n == 169)printf("1 9 30
"); if(n == 170)printf("1 9 30
"); if(n == 171)printf("1 9 30
"); if(n == 172)printf("1 12 31
"); if(n == 173)printf("1 12 31
"); if(n == 174)printf("1 12 31
"); if(n == 175)printf("1 12 31
"); if(n == 176)printf("1 10 34
"); if(n == 177)printf("1 10 34
"); if(n == 178)printf("1 10 34
"); if(n == 179)printf("1 10 33
"); if(n == 180)printf("1 10 34
"); if(n == 181)printf("1 10 34
"); if(n == 182)printf("1 10 34
"); if(n == 183)printf("1 10 34
"); if(n == 184)printf("1 10 34
"); if(n == 185)printf("1 10 34
"); if(n == 186)printf("1 10 34
"); if(n == 187)printf("1 10 34
"); if(n == 188)printf("1 12 31
"); if(n == 189)printf("1 12 31
"); if(n == 190)printf("1 12 31
"); if(n == 191)printf("1 12 31
"); if(n == 192)printf("1 12 31
"); if(n == 193)printf("1 12 31
"); if(n == 194)printf("1 12 31
"); if(n == 195)printf("1 12 31
"); if(n == 196)printf("1 12 31
"); if(n == 197)printf("1 17 27
"); if(n == 198)printf("1 12 31
"); if(n == 199)printf("1 12 31
"); if(n == 200)printf("1 12 31
"); } return 0;}// - xgtao - |
D - 柱爷的恋爱
题意：
给出一个包含") ( ] ["的括号序列,可以选择括号删除,但是不能全部删除,问有多少种方式让其成为合法的括号序列(%1000000007),
合法的括号序列定义如下:
- 如果S是合法序列,那(S)和[S]也是合法序列。
- 如果A和B都是合法序列,那么AB也是合法序列。
- (), [], (()), ([]), ()[], ()[()]。
题解：
0.因为如果A,B是合法的那么AB也是合法的,所以这是区间dp。
1.定义状态dp[i][j]表示在i~j这个区间内的合法方案数目。
2.状态转移种,括号面临两种决策,删还是不删。
3.如果删除当前的一个括号dp[i][j] = dp[i+1][j]。
4.如果不删除,但必须满足后面有一个括号能够和它匹配,如果i&k匹配那么[i+1,k-1]要合法,[k+1,j]也要合法 dp[i][j] += dp[i+1][k-1]*dp[k+1][j]。
5.因为计算的是dp[0][n-1]包含了把括号全部删除的情况,所以最后要+1。
代码：
|
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
|
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int mod = 1000000007;#define ll long longconst int N = 500;ll f[N][N];char bracket[N];int n,vis[N][N];bool flag(int l,int r){ if(bracket[l] == '(' && bracket[r] == ')')return true; if(bracket[l] == '[' && bracket[r] == ']')return true; return false;}ll dp(int l,int r){ if(vis[l][r])return f[l][r]; vis[l][r] = 1; if(l >= r)return f[l][r] = 1; f[l][r] = dp(l+1,r)%mod; for(int k = l;k <= r;++k){ if(!flag(l,k))continue; f[l][r] = (f[l][r]+dp(l+1,k-1)*dp(k+1,r))%mod; } return f[l][r]%mod;}int main(){ scanf("%d",&n); scanf("%s",bracket); cout<<(dp(0,n-1)-1)%mod<<endl; return 0;}// - xgtao - |
E - 柱爷与远古法阵
题意：
有一排长度为n(<=300)的格子,从1开始走到n,有一个骰子(1~6),每次可以走骰子的点数那么多的步数,并且中途会有一些传送门,求走到n点的期望数。
题解：
0.定义状态dp[x]表示从x点走到n的期望步数。
1.状态转移有两种情况,这个点有还是没有传送门。
2.是有传送门:dp[x] = dp[x']
3.没有传送门并且x <= n-6:由全期望公式得到dp[x] = (dp[x+1]+dp[x+2]+dp[x+3]+dp[x+4]+dp[x+5]+dp[x+6])/6 + 1;
4.没有传送门并且x > n-6也就是面临越界的情况dp[x] = (dp[x]+dp[x]+dp[x+1]+...dp[n])/6 + 1;因为越界了之后可以选择不走,它就转移到了自己,。
5.边界就是dp[n] = 0。
6.这里有n个点可以列出n个式子,那么就是n元一次方程,用高斯消元就可以解出dp[1]。
代码：
|
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
|
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>using namespace std;const long double eps = 1e-14;const int N = 400;int n,m,link[N],u,v;long double Gau[N][N];int main(){ scanf("%d%d",&n,&m); for(int i = 1;i <= n;++i)link[i] = i; for(int i = 1;i <= m;++i){ scanf("%d%d",&u,&v);link[u] = v; } for(int i = 1;i < n;++i){ Gau[i][i] = 6.0; if(link[i] != i)Gau[i][link[i]] = -6.0; else{ Gau[i][n+1] = 6.0; for(int j = 1;j <= 6;++j){ if(i+j <= n)Gau[i][i+j] = -1.0; else { Gau[i][i] -= 1.0; } } } } Gau[n][n] = 1.0; Gau[n][n+1] = 0; for(int i = 1;i <= n;++i){ int cur = i; for(int j = i+1;j <= n;++j)if(fabs(Gau[j][i])>eps)cur = j; if(fabs(Gau[cur][i])>eps){ for(int j = i;j <= n+1;++j)swap(Gau[i][j],Gau[cur][j]); for(int j = i+1;j <= n;++j){ if(fabs(Gau[j][i])<=eps)continue; long double coe = Gau[j][i]/Gau[i][i]; for(int k = i;k <= n+1;++k){ Gau[j][k] -= Gau[i][k]*coe; } } } } for(int i = n;i >= 1;--i){ for(int j = i+1;j <= n;++j){ if(fabs(Gau[i][j])<=eps)continue; Gau[i][n+1] -= Gau[i][j]*Gau[j][n+1]; } if(fabs(Gau[i][i])<=eps && fabs(Gau[i][n+1])>eps){ printf("-1
"); return 0; } Gau[i][n+1] /= Gau[i][i]; } printf("%.10lf
",(double)Gau[1][n+1]); return 0;}// - xgtao - |
F - 柱爷与三叉戟不得不说的故事
题意：
柱爷要修复三叉戟要15种元素,有两种方式,方式一：分别给出获得每一种元素的代价,方式二：分别给出获得一套元素的代价,要求一种元素不能重复获得,求最小代价。
题解：
0.数据范围是15,考虑状态压缩。
1.定义状态dp[S]表示获得S这个集合的元素的代价的最小值。
2.S是由其子集转移而来,状态转移dp[S] = min{dp[S0]+dp[S0^S]}。
代码：
|
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
|
#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 100010;int n;int dp[400010];int main(){ memset(dp,127,sizeof(dp)); for(int i = 0;i < 15;++i)scanf("%d",&dp[(1<<i)]); scanf("%d",&n); for(int i = 0;i < n;++i){ int m,x,set = 0; scanf("%d",&m); for(int j = 1;j <= m;++j){ scanf("%d",&x),set |= (1<<(x-1)); } scanf("%d",&x); dp[set] = min(dp[set],x); } int all = (1<<15); dp[0] = 0; for(int S = 0;S < all;++S){ for(int S0 = S;S0;S0 = (S0-1)&S)dp[S] = min(dp[S],dp[S0]+dp[S0^S]); } printf("%d
",dp[all-1]); return 0;}//- xgtao - |
G - 柱爷与三叉戟
题意：
给出一个数n(<=10^500),定义函数F(x)表示x转化成二进制后1的个数,求满足1<=i<j<=n && F(i)>F(j)的对数。
题解：
0.首先考虑最原始最暴力的解法,从1开始枚举i,从i+1开始枚举j,再计算F(i)和F(j),如果F(i)>F(j)那么答案+1,但是发现F(x)计算多次,就发现可以记忆化,那么就考虑数位dp。
1.首先把n转成2进制数。
2.从高位开始枚举两个数i,j,始终保持i<j,并且记录F(i)与F(j)的差值,到了最后一位如果差值>0,就返回1。
3.状态定义：dp[pos][ch][lia][lib][lic]表示从高位考虑到pos位F(i)与F(j)之差为ch的个数,lia是枚举i的限制条件,lib是枚举j的限制条件,lic表示i是否小于j。
4.因为差值在某一位置可能为负数为了防止dp下标为负数,所以一开始dfs差值为N(N为二进制10^500的位数)。
代码：
|
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
|
#include <cstdio>#include <string>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 1667;const int mod = 1000000007;string str;int dp[N+10][N*2+10][2][2][2];string BigINt(string x){ string ret = ""; string c = "2333"; while(c.length()){ c = ""; char ch; int i = 0; while(i < x.length()){ ch = x[i]-'0'; if(ch>=2)c += static_cast<char>(ch/2+'0'); else if(c.length())c += '0'; if(ch%2 == 1 && i < x.length()-1)x[i+1] += 10; ++i; } ret = ret+static_cast<char>(ch%2+'0'); x = c; } return ret;}int dfs(int pos,int ch,bool lia,bool lib,bool lic){ if(pos == str.length())return (lic == 1 && ch > N); if(dp[pos][ch][lia][lib][lic] != -1)return dp[pos][ch][lia][lib][lic]; int &ret = dp[pos][ch][lia][lib][lic] = 0; int end1 = lia ? str[pos]-'0' : 1; int end2 = lib ? str[pos]-'0' : 1; for(int i = 0;i <= end1;++i){ for(int j = 0;j <= end2;++j){ if(!lic && i > j)continue; ret = (ret+dfs(pos+1,ch+(i==1)-(j==1),lia&&i==end1,lib&&j==end2,lic||i<j))%mod; } } return ret%mod;}int main(){ cin>>str; str = BigINt(str); reverse(str.begin(),str.end()); memset(dp,-1,sizeof(dp)); printf("%d
",dfs(0,N,1,1,0)); return 0;}// - xgtao - |
H - 柱爷大战滑稽王
题意：
给出两个长度为n(<=1000000)序列A,B,(|Ai,Bi|<=10^9),保证同一序列数字不重复,求这两个序列的最长公共子序列。
题解：
0.每个数字数据范围太大需要离散。
1.把A中的每一个数字出现的位置记录下来,在B中把A中出现的数的位置按B排好。
也就是说 A: 1 5 6 9 4
B： 1 6 9 4 5 对应关系也就是：1在A中的位置是1，6在A中的位置是3，9在A中的位置是4，4在A中的位置是5，5在A中的位置是2。
对应得到 C: 1 3 4 5 2
2.问题转化为求C得LIS，LIS的O(nlogn),就是在一个序列中不断替换第一个大于等于当前的数,因为这样序列就更有延展性,答案保证不会差,但是并不一定是这一个序列,但是长度一定相同的。
代码：
|
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
|
#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 1000001;int n,m,x,cnt,ans,p[N],g[N],dp[N],id[N],c[N],ncnt,hase[N];int main(){ scanf("%d%d",&n,&m); for(int i = 1;i <= n;++i){ scanf("%d",&c[i]); hase[++ncnt] = c[i]; } sort(hase+1,hase+ncnt+1); for(int i = 1;i <= n;++i){ int l = lower_bound(hase+1,hase+1+ncnt,c[i])-hase; id[l] = i; } for(int i = 1;i <= m;++i){ scanf("%d",&x); int l = lower_bound(hase+1,hase+1+ncnt,x)-hase; if(hase[l] != x)continue; p[++cnt] = id[l]; } memset(g,127,sizeof(g)); for(int i = 1;i <= cnt;++i){ int k = lower_bound(g+1,g+cnt+1,p[i])-g; dp[i] = k; g[k] = p[i]; ans = max(ans,dp[i]); } cout<<ans+1<<endl; return 0;}// - xgtao - |
I - 柱爷抢银行
题意：
给出n*m的矩阵,表示aij表示i行j列的金钱数目,如果aij<0,如果选择了这点会损失abs(aij)，如果aij>0,就可以直接得到钱,柱爷因为实力很强所以要走一个联通块,柱爷不是个退缩的人！来了就要抢。
题解：
0.状态定义：dpl[i][j]表示在i行j列向左走能够得到的最大值,dpr[i][j]表示在i行j列向右走的最大值，dpu[i][k]表示链接(i,k)这个点的上面的联通块的最大值。
1.状态转移：dpl,dpr不难写出dpl[i][j+1] = max{dpl[i][j]+mat[i][j+1]} dpr[i][j-1] = max{dpr[i][j]+mat[i][j-1]}
2.状态转移：dpu有两种决策
①:dpu[i+1][j] = max{dpu[i][k]+sum[j]-sum[k-1]+dpr[i][j+1]+dpl[i][k-1]} = max{dpu[i][k]-sum[k-1]+dpl[i][k-1]}+sum[j]+dpr[i][j+1]}
也就是当(k<=j)时维护max{dpu[i][k]-sum[k-1]+dpl[i][k-1]}
②:dpu[i+1][j] = max{dpu[i][k]+sum[k]-sum[j-1]+dpr[i][k+1]+dpl[i][j-1]} = max{dpu[i][k]+sum[k]+dpr[i][k+1]}-sum[j-1]+dpl[i][j-1]}
也就是当(k>=j)时维护max{dpu[i][k]+sum[k]+dpr[i][k+1]}
3.答案也就是max{dpu[i+1][j],dpl[i][j-1]+mat[i][j]+dp[i][j+1]}
4.如果为空集的话就特判一下。
代码：
|
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
|
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define ll long longconst int N = 1010;const ll inf = 1e20;int n,m,flag;ll sum[N][N],dpl[N][N],dpr[N][N],dpu[N][N],maxg,mat[N][N],maxp,ret;int main(){ scanf("%d%d",&n,&m); maxp = ret = maxg = -inf; for(int i = 1;i <= n;++i){ for(int j = 1;j <= m;++j){ cin>>mat[i][j]; if(!flag && mat[i][j]>0)flag = 1; maxg = max(maxg,mat[i][j]); sum[i][j] = sum[i][j-1]+mat[i][j]; } } for(int i = 1;i <= n;++i){ for(int k = 1;k <= m;++k){ dpl[i][k] = max(dpl[i][k],mat[i][k]); dpl[i][k+1] = max(dpl[i][k+1],dpl[i][k]+mat[i][k+1]); } for(int k = m;k >= 1;--k){ dpr[i][k] = max(dpr[i][k],mat[i][k]); dpr[i][k-1] = max(dpr[i][k-1],dpr[i][k]+mat[i][k-1]); } maxp = -inf; for(int k = 1;k <= m;++k){ maxp = max(maxp,dpu[i][k]-sum[i][k-1]+dpl[i][k-1]); dpu[i+1][k] = max(dpu[i+1][k],maxp+sum[i][k]+dpr[i][k+1]); ret = max(ret,dpl[i][k-1]+mat[i][k]+dpr[i][k+1]); ret = max(ret,dpu[i+1][k]); } maxp = -inf; for(int k = m;k >= 1;--k){ maxp = max(maxp,dpu[i][k]+sum[i][k]+dpr[i][k+1]); dpu[i+1][k] = max(dpu[i+1][k],maxp-sum[i][k-1]+dpl[i][k-1]); ret = max(ret,dpl[i][k-1]+mat[i][k]+dpr[i][k+1]); ret = max(ret,dpu[i+1][k]); } } if(!flag && ret == 0)ret = maxg; cout<<ret<<endl; return 0;} // - xgtao - |
J - 柱爷抢银行II
题意：
有n(<=1000000)个银行是按照顺时针的圈排布,给出在每个银行可以抢多少钱,柱爷决定选择不超过长度为k(<=1000000)的区间里面抢钱,求最多能抢多少？柱爷不是个退缩的人！来了就要抢！
题解：
0.既然是环,那么就需要断环为链。
1.定义状态dp[i]表示在i点之前长度不超过k的区间最大和。
2.状态转移很容易想到dp[i] = max{dp[i-1],sum[i]-sum[j-1]}(i-k+1<=j<=i) 复杂度为O(n*k),这个复杂度伤不起。
3.就用单调递增队列维护sum[j-1],单调队列的头就是最优sum的下标。注意维护的下标是j-1
代码：
|
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
|
#include <cstdio>#include <iostream>#include <algorithm>using namespace std;const int N = 4000000;int n,k,a[N],sum[N],dp[N],ansl,ansr;class singlequeue{protected: int q[N],head,tail;public: void pop_back(){--tail;} void pop_front(){++head;} int back(){return q[tail];} int front(){return q[head];} int size(){return tail-head+1;} void push_back(int x){q[++tail] = x;} void init(){head = 0,tail = -1;} bool empty(){return tail-head+1>0 ? 0 : 1;} singlequeue(){init();}}sq;int main(){ scanf("%d%d",&n,&k); for(int i = 1;i <= n;++i){ scanf("%d",&a[i]),a[n+i] = a[i]; } for(int i = 1;i <= 2*n;++i){ sum[i] = sum[i-1]+a[i]; } sq.init();ansl = ansr = 1; sq.push_back(1); dp[1] = sum[1]; for(int i = 2;i <= 2*n;++i){ while(!sq.empty() && sq.front() < i-k) sq.pop_front(); if(dp[i-1] < sum[i]-sum[sq.front()]){ dp[i] = sum[i]-sum[sq.front()]; ansl = sq.front() + 1; ansr = i; } else dp[i] = dp[i-1]; while(!sq.empty() && sum[i] < sum[sq.back()])sq.pop_back(); sq.push_back(i); } printf("%d %d %d
",dp[2*n],ansl>n?ansl-n:ansl,ansr>n?ansr-n:ansr); return 0;}// - xgtao - |
K - 柱爷抢银行III
题意：
给出一棵树,节点数<=500,每一个节点代表一个银行,柱爷抢银行太熟练所以抢银行不会消耗精力,但是柱爷从一个银行到另外一个银行会消耗精力,有q个询问,给出一开始柱爷的精力,问柱爷从0号点出发最多能抢几家银行？
题解：
0.不难看出这是一个树形dp,定义状态dp[u][i][0/1]表示在根节点为u的子树中抢i家银行并且当前是否在i这个节点最小的精力消耗。
1.状态转移:dp[u][i+k][0] = max{dp[u][i][1]+dp[v][k][1]+w,dp[u][i][0]+dp[v][k][1]+2*w,dp[u][i][1]+dp[v][k][0]+w}
dp[u][i+k][1] = max{dp[u][i][1]+dp[v][k][1]+2*w}
2.最后只需倒序枚举节点数,找到第一个小于等于原始精力的min{dp[0][i][1],dp[0][i][0]}，输出i。
代码：
|
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 <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 510;struct edge{ int v,w; edge *nxt;}*head[N],*cur,Edge[N*2];int dp[N][N][2],size[N],n,u,v,w,q,x;void addedge(int u,int v,int w){ cur->v = v; cur->w = w; cur->nxt = head[u]; head[u] = cur++;}int dfs(int u,int fa){ dp[u][1][1] = 0; size[u] = 1; for(edge *it = head[u];it;it = it->nxt){ int v = it->v; if(v == fa)continue; size[v] = dfs(v,u); for(int i = size[u];i >= 1;--i){ for(int k = size[v];k >= 1;--k){ dp[u][i+k][0] = min(dp[u][i+k][0],dp[u][i][0]+dp[v][k][1]+2*it->w); dp[u][i+k][0] = min(dp[u][i+k][0],dp[u][i][1]+dp[v][k][0]+1*it->w); dp[u][i+k][0] = min(dp[u][i+k][0],dp[u][i][1]+dp[v][k][1]+1*it->w); dp[u][i+k][1] = min(dp[u][i+k][1],dp[u][i][1]+dp[v][k][1]+2*it->w); } } size[u] += size[v]; } return size[u];}int main(){ cur = Edge; scanf("%d",&n); for(int i = 0;i < n-1;++i){ scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } scanf("%d",&q); memset(dp,127,sizeof(dp)); dfs(0,-1); while(q--){ scanf("%d",&x); for(int i = n;i >= 1;--i){ if(min(dp[0][i][0],dp[0][i][1])<=x){ printf("%d
",i); break; } } } return 0;}// - xgtao - |
L - 柱爷抢银行MkⅣ
题意：
一条街上有n(<=100000)个银行,对于第i个银行位置是x[i](<=109),钱是w[i](<=109),并且对于i号银行,只有位置比i小y[i]以内的银行才能到i。柱爷不是个退缩的人！来了就要抢！
题解：
0.因为位置的数据范围太大,需要离散,再把银行按照位置从小到大排序。
1.定义状态dp[i]表示到达i号银行所得的最多的钱数。
2.状态转移dp[i] = max{dp[j]+w[i]}(i-y[i]<=j<i)复杂度为O(n*n)所以需要优化。
3.用线段树维护区间[i-y[i],i]这个区间里的极大值,再单点修改i点的极大值
4.转台转移即为dp[i] = query(1,1,n,i-y[i],i)+w[i],修改即为update(1,1,n,i,dp[i])
代码：
|
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
|
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define ll long longconst int N = 100010;struct gg{ll v;int x,y;}bank[N];int hase[N],cnt;ll maxi[N<<2],n,dp[N];ll query(int k,int l,int r,int L,int R){ if(L <= l && R >= r)return maxi[k]; int mid = (l+r)>>1; ll ret = 0; if(L <= mid)ret = max(ret,query(k<<1,l,mid,L,R)); if(R > mid)ret = max(ret,query(k<<1|1,mid+1,r,L,R)); return ret;}void update(int k,int l,int r,int x,ll w){ if(l == r){ maxi[k] = max(maxi[k],w); return; } int mid = (l+r)>>1; if(x <= mid)update(k<<1,l,mid,x,w); else if(x > mid)update(k<<1|1,mid+1,r,x,w); maxi[k] = max(maxi[k<<1],maxi[k<<1|1]);}int main(){ scanf("%d",&n); for(int i = 1;i <= n;++i){ scanf("%d%d%d",&bank[i].x,&bank[i].v,&bank[i].y); hase[++cnt] = bank[i].x; } sort(hase+1,hase+1+cnt); cnt = unique(hase+1,hase+cnt+1)-hase-1; for(int i = 1;i <= n;++i){ int r = lower_bound(hase+1,hase+1+cnt,bank[i].x)-hase; int l = lower_bound(hase+1,hase+1+cnt,bank[i].x-bank[i].y)-hase; dp[i] = bank[i].v+query(1,1,cnt,l,r); update(1,1,cnt,r,dp[i]); } ll ans = 0; for(int i = 1;i <= n;++i)ans = max(ans,dp[i]); cout<<ans<<endl; return 0;}// - xgtao - |
M - 柱爷抢银行欢庆5.1special
题意：
给出一个n*m(<=500)的方阵,方阵中的每个格子都有一家银行，柱爷抢这家银行能得到aij的钱，当aij<0柱爷会损失的钱。他决定要抢的银行要形成k阶顺时针螺旋状，其中k为≥3的任意奇数。下面是k=3,5,7的图形，其中黑色方块是柱爷要抢钱的银行。求最多抢的钱数，柱爷不是个退缩的人！来了就要抢！
题解：
0.很容易观察出pic3的白色部分和pic2的黑色部分形状是一样的,只不过多了那一小块。
1.定义状态：dp[i][j][k]表示以(i,j)这个点为左上角并且当前是第k阶的黑色部分的和,但是500*500*500会爆,所以要滚动~
2.状态转移：dp[i][j][x] = gs(i,j,i+k-1,j+k-1)-dp[i+1][j+1][x^1]-mat[i+1][j] (k = 3;k <= min(n,m);k+=2)
代码：
|
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
|
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 510;int sum[N][N],n,m,mat[N][N],dp[N][N][2];int gs(int x,int y,int i,int j){ return sum[i][j]-sum[x-1][j]-sum[i][y-1]+sum[x-1][y-1];}int main(){ scanf("%d%d",&n,&m); int x = 1; for(int i = 1;i <= n;++i){ for(int j = 1;j <= m;++j){ scanf("%d",&mat[i][j]); dp[i][j][x] = mat[i][j]; sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+mat[i][j]; } } int ans = -1e9; for(int k = 3;k <= min(m,n);k+=2){ x ^= 1; for(int i = 1;i+k-1 <= n;++i){ for(int j = 1;j+k-1 <= m;++j){ dp[i][j][x] = gs(i,j,i+k-1,j+k-1)-dp[i+1][j+1][x^1]-mat[i+1][j]; ans = max(ans,dp[i][j][x]); } } } cout<<ans<<endl; return 0;}// - xgtao - |
N - 柱爷与子序列
题意：
给出一个长度为n(<=100000)的序列A,Ai<=10^9,求出一共有多少组完美子序列(长度>=2,下标呈升序,相邻两数差的绝对值小于一个数k),对1000000009取模。
题解：
0.数据太大，肯定需要离散。
1.状态定义：dp[i]表示以A[i]结尾的完美子序列的个数。
2.状态转移：dp[i] += dp[j](abs(A[j]-A[i]) <= k && 1 <= j < i),复杂度O(n^2)所以要优化。
3.用树状数组离散后的序列,以值为下标,那么能够与A[i]对接的就是A[i]-k ~ A[i]+k 这段区间,树状数组维护的是一个以1~某个值结尾前缀和。
4.状态转移：dp[x] += query(x+k)-query(x-k-1), update(x,dp[x]+1);
5.最后把dp[]求和。
代码：
|
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
|
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 100010;const int mod = 1000000009;#define lowbit(i) i&-i#define ll long longll c[N],ret;int a[N],cnt,hase[N],n,k;ll query(int x){ ll ret = 0; for(int i = x;i >= 1;i -= lowbit(i)){ ret = (ret+c[i])%mod; ret = (ret+mod)%mod; } return ret;}void update(int x,ll p){ for(int i = x;i <= N;i += lowbit(i)){ c[i] = (c[i]+p)%mod; c[i] = (c[i]+mod)%mod; }}int main(){ scanf("%d%d",&n,&k); for(int i = 1;i <= n;++i){ cin>>a[i]; hase[++cnt] = a[i]; } sort(hase+1,hase+cnt+1); cnt = unique(hase+1,hase+cnt+1)-hase-1; for(int i = 1;i <= n;++i){ int x = lower_bound(hase+1,hase+1+cnt,a[i])-hase; int l = lower_bound(hase+1,hase+1+cnt,a[i]-k)-hase; int r = upper_bound(hase+1,hase+1+cnt,a[i]+k)-hase;--r; ll c = query(r)-query(l-1);//c可能为负数因为query(r)被%,query(l-1)还没有被% ret = (ret+c)%mod; ret = (ret+mod)%mod; update(x,c+1); } cout<<ret<<endl; return 0;}// - xgtao - |
O - 柱爷很忙
题意：
给出n(n<=1000)件事情的类型ai和重要性bi(<=7),事情可以推后,但是一件事情为K,并且K>i+b[i]则k就不能放在i之前做完,如果要做事情类型为i，前一件做的事情为j,那么要花费的时间为(a[i]|a[j])-(a[i]&a[j]),求做完事情的最短时间。
题解：
0.b的数据范围才7,考虑状态压缩。
1.定义状态：dp[i][S][d]第一维表示以第i件事情结尾,第二维表示以i结尾的最后8件事情的完成情况为S,第三维d表示上一件做的事情离i的距离,dp表示最短的时间
2.状态转移：有两种决策：
①对于以i结尾的8件事情先不慌,往后推,dp[i+1][S^(1<<7)<<1][min(d+1,16)] = min{dp[i][S][d]};(条件是以i结尾的8件事情中最早的那一件事情先做完)
②对于以i结尾的8件事情要做,dp[i][S|(1<<k)][k] = min{dp[i][S][l]+((d==16)?a[i-k]:(a[i-k]|a[i-d])-(a[i-k]&a[i-d])};(条件是离i的距离为k的那件事情没有做过,并且要把不能再拖的事情做了)
(注意d最多为15,d == 16是因为特判第一件事情)。
代码：
|
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
|
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int all = 1<<8;const int inf = 0x7f7f7f7f;const int N = 1616;int n,a[N],b[N],dp[N][all][21];int main(){ scanf("%d",&n); memset(dp,0x7f,sizeof(dp)); for(int i = 1;i <= n;++i)cin>>a[i]>>b[i]; dp[0][all-1][16] = 0; for(int i = 0;i <= n;++i) for(int S = 0;S < all;++S) for(int d = 0;d <= 16;++d) if(dp[i][S][d] != inf){ int p = min(i,8),putoff = inf; for(int k = p-1;k >= 0;--k){ if( ((S>>k)&1) == 0 )putoff = min(putoff,i-k+b[i-k]); } if( ((S>>7)&1) == 1){ dp[i+1][(S^(1<<7))<<1][min(d+1,16)] = min(dp[i+1][(S^(1<<7))<<1][min(d+1,16)],dp[i][S][d]); } for(int k = p-1;k >= 0 && i<=putoff+k;--k){ if(((S>>k)&1) == 0){ dp[i][S|(1<<k)][k] = min(dp[i][S|(1<<k)][k],dp[i][S][d]+((d==16)?a[i-k]:(a[i-k]|a[i-d])-(a[i-k]&a[i-d]))); } } } int ret = inf; for(int i = 0;i <= 16;++i)ret = min(ret,dp[n][all-1][i]); cout<<ret<<endl; return 0;}// - xgtao - |
P - 柱爷的矩阵
题意：
给出矩阵的行数n(<=1000),给出每一行第一个数a[i]，再给出每一行的b[i],a[i][j+1] = a[i][j]-b[i],在每一行每一列取至多一个数,求取出的数和最大。
题解：
0.对于要去第i行,第j行的数字并且b[i]>b[j]要先考虑第i行的那个数字,所以要按照b从大到小排序。
1.状态定义：dp[i][j][0/1],dp[i][j][0]表示不一定选了(i,j)这个位置的数字,也就是说所选的数字在k1(k1<=i)行的k2列(k2<=j)处,dp[i][j][1]必定选(i,j)这个位置的数字时的最大值。
2.状态转移：dp[i][j][1] = dp[i-1][j-1][0]+max(0,a[i]-(j-1)*b[i])
dp[i][j][0] = max{dp[i-1][j][0],dp[i][j-1],dp[i][j][1]}
代码：
|
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
|
#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 1010;int dp[N][N][2],n,m;struct node{ int a,b; bool operator < (const node &rhs)const{ return b > rhs.b; }}x[N];int main(){ scanf("%d%d",&n,&m); for(int i = 1;i <= n;++i)scanf("%d",&x[i].a); for(int i = 1;i <= n;++i)scanf("%d",&x[i].b); sort(x+1,x+n+1); for(int j = 1;j <= m;++j){ for(int i = 1;i <= n;++i){ dp[i][j][1] = dp[i-1][j-1][0]+max(0,x[i].a-(j-1)*x[i].b); dp[i][j][0] = max(dp[i-1][j][0],dp[i][j-1][0]); dp[i][j][0] = max(dp[i][j][0],dp[i][j][1]); } } cout<<dp[n][m][0]<<endl; return 0;}// - xgtao - |
Q - 柱爷的宝藏
题意：
给出一个长度为n(<=500000)的序列,把这个序列分成任意多个区间,如果某个区间有{a[x]，a[x+1]，...a[y]},那么这个区间的权值为(a[x]+a[x+1]+...a[y])^2+m,怎么划分使得整个序列的区间权值和最小，求最小权值。
题解：
0.定义状态：dp[i]表示前i个数的组成序列的所有区间的权值和。
1.状态转移：dp[i] = min{dp[j]+(sum[i]-sum[j])^2+m}(1<=j<i)复杂度为O(n^2)超时！
2.斜率优化！！
①假设k<j<i如果j比k优,那么dp[j]+(sum[i]-sum[j])^2+m<dp[k]+(sum[i]-sum[k])^2+m化简后得到式子[(dp[j]+sum[j]^2)-(dp[k]+sum[k]^2)]/(2*sum[j]-2*sum[k])<sum[i],令dp[]+sum[]^2为y[]，令2*sum[x]为x[],那么将x[],y[]带入原式,则g[j,k] = (y[j]-y[k])/(x[j]-x[k])<sum[i]。
②那么反过来如果g[j,k]<sum[i],就可以得到j一定比k优，再反过来g[j,k]>sum[i]那么k一定比j优,如果g[j,k] = sum[i]那么k一定不会比j差
③从左到右a<b<c<i,如果g[b,a]>=g[c,b],那么b永远不可能为最优解,证明需要分类讨论
假设sum[i]>=g[b,a]>=g[c,b]这种情况下c优于b优于a或者b一起优，但是我们也可以不选b啊 
假设g[b,a]>=sum[i]>=g[b,c]这种情况是a优于b优于c或者b一起优，但是我们也可以不选b啊
假设g[b,a]>=g[c,b]>=sum[i]这种情况是a优于b优于c或者b一起优，但是我们也可以不选b啊
总而言之每一种情况下b都不可能成为最优的。
④排除了g[b,a]>g[c,b]这种情况之后,就只剩下g[b,a]<=g[c,b]的情况,那么斜率整个就成一个单调递增的了。
⑤用一个单调队列来维护斜率。
⑥入队的时候如果队列中已经有a,b,c,d,e五个元素了,现在f需要进队但是如果g[e,d]>=g[f,e]那么e就出队,直到满足单调递增为止
⑦求解的时候如果队列中已经有a,b,c,d,e五个元素了,如果g[b,a]<=sum[i]a就排除,a就出队,直到找到一个g[head+1,head]>=sum[i]为止
代码：
|
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
|
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define ll long long#define square(i) ((i)*(i))const int N = 500010;ll dp[N],sum[N],n,m,x,sq[N];ll deltay(ll i,ll j){ return dp[i]-dp[j]+square(sum[i])-square(sum[j]);}ll deltax(ll i,ll j){ return sum[i]-sum[j] <<1;}int main(){ cin>>n>>m; for(int i = 1;i <= n;++i){ cin>>x; sum[i] = sum[i-1]+x; } int head = 0,tail = -1; for(int i = 1;i <= n;++i){ while(tail-head+1>0 && deltay(sq[head+1],sq[head])<=deltax(sq[head+1],sq[head])*sum[i])++head; dp[i] = dp[sq[head]]+square(sum[i]-sum[sq[head]])+m; while(tail-head+1>0 && deltay(i,sq[tail])*deltax(sq[tail],sq[tail-1])<=deltay(sq[tail],sq[tail-1])*deltax(i,sq[tail]) )--tail; sq[++tail] = i; } cout<<dp[n]<<endl; return 0;}// - xgtao - |
R - 柱爷把妹（吃惊高清重制版）
题意：
柱爷通过PY交易,知道了接下来n天的股市行情,第i天买入卖出的的价格为Pi,每天柱爷可以买卖或者不动,但是买卖一次会交F的手续费,买之前扣,卖之后扣,柱爷也有一定的本金m,求最大收益。
题解：
0.定义状态：dp[i][0/1]，dp[i][0]表示第i天不做任何操作拥有的钱,dp[i][1]表示第i天操作后有的钱
1.
①假设p[a]<p[b]<p[c]。
②分析a->b(a天买b天卖)moneya-b = (m-F)/p[a]*p[b]-F+(m-F)%p[a]
③分析a->c(a天买c天卖)moneya-c = (m-F)/p[a]*p[c]-F+(m-F)%p[a]
④分析a->b->c moneya-b-c = (moneya-b+F)/p[b]*p[c]-F+(moneya-b+F)%p[b] = {(m-F)/p[a]*p[b]+(m-F)%p[a]}/p[b]*p[c]-F+{(m-F)/p[a]*p[b]+(m-F)%p[a]}%p[b]
因为p[a]<p[b]所以(m-F)%p[a]/p[b]为0,又因为(m-F)/p[a]*p[b]%p[b]等于0，所以moneya-c = (m-F)/p[a]*p[c]-F+(m-F)%p[a];
⑤所以得到结论moneya-b-c = moneya-c;
2.状态转移:
①dp[nxt[i]][1] = max{(dp[i][0]-F)/p[i]*p[nxt[i]]-F+(dp[[i][0]-F)%p[i],(dp[i][1]+F)/p[i]*p[nxt[i]]-F+(dp[i][1]-F)%p[i]}(p[nxt[i]]>p[i])
②dp[i+1][0] = max{dp[i][0],dp[i][1]}
③dp[nxt[i]][0] = max{dp[i][0],dp[i][1]}
3.预处理出nxt[i]就解决问题了。
代码：
|
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
|
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define ll long longconst int N = 100010;ll dp[N][2];int Stack[N],p[N],nxt[N],n,m,f;int main(){ cin>>n>>m>>f; for(int i = 1;i <= n;++i)cin>>p[i]; int top = 0;Stack[top] = n; for (int i = n; i; --i){ while (top && p[i] >= p[Stack[top]])--top; nxt[i] = top?Stack[top]:i; Stack[++top] = i; } memset(dp,128,sizeof(dp)); dp[1][0] = m;ll tmp,ans = 0; for(int i = 1;i <= n;++i){ ans = max(ans,max(dp[i][0],dp[i][1])); dp[i+1][0] = max(dp[i+1][0],max(dp[i][0],dp[i][1])); dp[nxt[i]][0] = max(dp[nxt[i]][0],max(dp[i][0],dp[i][1])); if(nxt[i] <= i)continue; tmp = dp[i][0]-f; if(tmp > 0)dp[nxt[i]][1] = max(dp[nxt[i]][1],tmp/p[i]*p[nxt[i]]+tmp%p[i]-f); tmp = dp[i][1]+f; if(tmp > 0)dp[nxt[i]][1] = max(dp[nxt[i]][1],tmp/p[i]*p[nxt[i]]+tmp%p[i]-f); } cout<<ans<<endl; return 0;}// - xgtao - |