五维的DP
g[i][D][r][s][p]
i: 到了第i个位置
D: 最后有D个点放在后面
r,s,p: 已经选择了r,s,p个石头,剪刀,布放到后面
四维的DP
f[i][D][r][s][p]
i: 到了第i个位置
D: 目前有D个点放在后面
r,s,p: 已经选择了r,s,p个石头,剪刀,布放到后面
其中D=r+s+p，从而减去一维
注意，放到后面的r,s,p，它们可以有不同的顺序，并不是按照数字编号的顺序往后放。
初始化，DP的时候，实际上不需要10^2^4，因为R+S+P=N，总执行数R*S*P*N最多是100*33*33*34。
注意边界初始化
别人题解
我的代码、数据 和 暴力造数据、获得结果
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define LL long long
4 #define ULL unsigned long long
5
6 const LL mod_1=1e9+7;
7 const LL mod_2=998244353;
8
9 const double eps_1=1e-5;
10 const double eps_2=1e-10;
11
12 const int maxn=1e2+10;
13
14 int f[maxn][maxn][maxn][maxn],qa[maxn],qb[maxn],prea[3][maxn],preb[3][maxn], n;
15 char str[maxn];
16
17 int cal(int x, int y)
18 {
19 if ((x+1)%3==y)
20 return 1;
21 return 0;
22 }
23
24 int getv(array<int,3> arr)
25 {
26 int u=arr[0]+arr[1]+arr[2], value=0, i,ii;
27
28 for (i=0;i<3;i++)
29 {
30 ii=(i+1)%3;
31 value += min(arr[i], preb[ii][n]-preb[ii][n-u]);
32 }
33
34 return value;
35 }
36
37 int main()
38 {
39 int i,j,r,s,p,u,result=0,cur_v;
40
41 scanf("%d",&n);
42
43 scanf("%s",str+1);
44 for (i=1;i<=n;i++)
45 {
46 if (str[i]=='r')
47 qa[i]=0;
48 else if (str[i]=='s')
49 qa[i]=1;
50 else
51 qa[i]=2;
52 }
53
54 scanf("%s",str+1);
55 for (i=1;i<=n;i++)
56 {
57 if (str[i]=='r')
58 qb[i]=0;
59 else if (str[i]=='s')
60 qb[i]=1;
61 else
62 qb[i]=2;
63 }
64
65 for (j=0;j<2;j++)
66 prea[j][0]=0;
67 for (i=1;i<=n;i++)
68 {
69 for (j=0;j<3;j++)
70 prea[j][i]=prea[j][i-1];
71 prea[ qa[i] ][i]++;
72 }
73
74 for (j=0;j<2;j++)
75 preb[j][0]=0;
76 for (i=1;i<=n;i++)
77 {
78 for (j=0;j<3;j++)
79 preb[j][i]=preb[j][i-1];
80 preb[ qb[i] ][i]++;
81 }
82
83
84 /*
85 for (i=1;i<=n;i++)
86 for (r=0;r<=prea[0][i];r++)
87 for (s=0;s<=prea[1][i];s++)
88 for (p=0;p<=prea[2][i];p++)
89 f[i][r][s][p]=-210;
90 */
91 ///try prea[0][n]+5 -> couldn't
92 for (i=0;i<=n;i++)
93 for (r=0;r<=prea[0][n];r++)
94 for (s=0;s<=prea[1][n];s++)
95 for (p=0;p<=prea[2][n];p++)
96 f[i][r][s][p]=-1000;
97 f[0][0][0][0]=0;
98 ///max: 100*33*33*34=3,702,600
99 ///内存也可以这样减少
100
101 for (i=1;i<=n;i++)
102 for (r=0;r<=prea[0][i];r++)
103 for (s=0;s<=prea[1][i];s++)
104 for (p=0;p<=prea[2][i];p++)
105 {
106 u=r+s+p;
107 cur_v = getv({r,s,p});
108
109 if (r<=prea[0][i-1] && s<=prea[1][i-1] && p<=prea[2][i-1])
110 f[i][r][s][p] = f[i-1][r][s][p] + cal(qa[i],qb[i-u]);
111
112 if (r>0 && qa[i]==0)
113 f[i][r][s][p] = max(f[i][r][s][p],
114 f[i-1][r-1][s][p] + cur_v - 1 - getv({r-1,s,p}) );
115
116 if (s>0 && qa[i]==1)
117 f[i][r][s][p] = max(f[i][r][s][p],
118 f[i-1][r][s-1][p] + cur_v - 1 - getv({r,s-1,p}) );
119
120 if (p>0 && qa[i]==2)
121 f[i][r][s][p] = max(f[i][r][s][p],
122 f[i-1][r][s][p-1] + cur_v - 1 - getv({r,s,p-1}) );
123 }
124
125 for (r=0;r<=prea[0][n];r++)
126 for (s=0;s<=prea[1][n];s++)
127 for (p=0;p<=prea[2][n];p++)
128 result = max(result, f[n][r][s][p]);
129
130 printf("%d\n",result);
131
132 return 0;
133 }
134 /*
135
136 6
137 pssrss
138 rrsppr
139
140 ------
141 3
142 wrong 4
143
144
145
146 6
147 ssrpps
148 rpssps
149
150 ------
151 2
152 wrong 3
153
154
155
156
157
158 ======
159
160 2
161 rs
162 ps
163
164 f[1][0][0][0]=0
165 f[1][1][0][0]=0
166
167 ======
168
169 5
170 rrrrr
171 sssss
172
173 =====
174
175 5
176 sssss
177 rrrrr
178
179 =====
180
181
182 10
183 rspprsprps
184 spprssrppr
185
186
187 ~~~~~~~~~
188
189 rsppr"sp"rps
190 spprssrppr
191
192
193
194 rspprrps"sp"
195 spprssrppr
196
197
198 f[5][0][0][0]=4
199 f[6][0][1][0]=3
200 f[7][0][1][1]=4
201 f[8][0][1][1]=5
202 f[9][0][1][1]=6
203
204
205 f[9][0][1][1]=6
206 i==9 && r==0 && s==1 && p==1
207
208
209
210 ======
211
212
213 10
214 rspprsprps
215 spprssrppr
216
217 10
218 sprrsprsrp
219 prrsppsrrs
220
221 10
222 prssprspsr
223 rssprrpssp
224
225 ======
226
227 1
228 r
229 s
230
231 1
232 r
233 p
234
235 ======
236
237 10 rrrrrrrrrr
238 20 rrrrrrrrrrrrrrrrrrrr
239 40 rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
240 80 rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
241 100 rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
242
243 pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
244
245
246 100
247 pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
248 rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
249
250
251 100
252 rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
253 rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
254
255
256 ======
257
258
259 6
260 sppsss
261 rpsrrs
262
263 ------
264 1
265 wrong 2
266
267
268
269 6
270 pssrss
271 rrsppr
272
273 ------
274 3
275 wrong 4
276
277
278
279 6
280 ssrpps
281 rpssps
282
283 ------
284 2
285 wrong 3
286
287
288
289
290 6
291 rpppsp
292 rppsrs
293
294 ------
295 2
296 wrong 3
297
298
299
300 10
301 prpprrpsps
302 ssrppprrsp
303
304 ------
305 4
306 wrong 6
307
308
309
310
311 10
312 sppsrrppsr
313 spsrsrsprr
314
315 ------
316 4
317 wrong 5
318
319
320
321
322 */
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define LL long long
4 #define ULL unsigned long long
5
6 const LL mod_1=1e9+7;
7 const LL mod_2=998244353;
8
9 const double eps_1=1e-5;
10 const double eps_2=1e-10;
11
12 const int maxn=2e4+10;
13
14 int n=6,result=0;
15 int a[maxn],b[maxn];
16 char ch[3]={'r','s','p'};
17
18 bool vis[maxn];
19 int last[maxn],a_new[maxn];
20
21 char str[maxn];
22 bool use_test1=0,test11=1,test12=1;
23
24 void build_data()
25 {
26 int i;
27 for (i=1;i<=n;i++)
28 {
29 a[i]=rand()%3;
30 b[i]=rand()%3;
31 }
32
33 printf("%d\n",n);
34 for (i=1;i<=n;i++)
35 printf("%c", ch[ a[i] ]);
36 printf("\n");
37 for (i=1;i<=n;i++)
38 printf("%c", ch[ b[i] ]);
39 printf("\n");
40 }
41
42 int cal_a_new_b(int step)
43 {
44 int i,r=0;
45 for (i=1;i<=n;i++)
46 if ((a_new[i]+1)%3==b[i])
47 r++;
48 return r-step;
49 }
50
51 int cal(int step)
52 {
53 int i,j=0;
54 if (use_test1)
55 {
56 if (step==2 && test11 && test12)
57 printf("ok\n");
58 }
59
60
61 for (i=1;i<=n;i++)
62 if (!vis[i])
63 a_new[++j] = a[i];
64 for (i=0;i<step;i++)
65 a_new[n-step+1+i] = a[ last[i] ];
66
67 return cal_a_new_b(step);
68 }
69
70 void dfs(int step)
71 {
72 int i;
73 result = max(result, cal(step));
74
75 for (i=1;i<=n;i++)
76 if (!vis[i])
77 {
78 if (use_test1)
79 {
80 if (step==0)
81 {
82 if (i==5)
83 test11=1;
84 else
85 test11=0;
86 }
87 if (step==1)
88 {
89 if (i==6)
90 test12=1;
91 else
92 test12=0;
93 }
94 }
95
96 vis[i]=1;
97 last[step]=i;
98
99 dfs(step+1);
100
101 vis[i]=0;
102 }
103 }
104
105 void get_result()
106 {
107 memset(vis,0,sizeof(vis));
108 result = 0;
109 dfs(0);
110 printf("%d\n",result);
111 }
112
113 int main()
114 {
115 srand(time(NULL));
116
117 int i;
118 int mode=2;
119 int T=10;
120
121 if (mode==1)
122 {
123 while (T--)
124 {
125 build_data();
126
127 printf("\n------\n");
128
129 get_result();
130
131 printf("\n\n======\n\n");
132
133 }
134 }
135 else if (mode==2)
136 {
137 scanf("%d",&n);
138
139 scanf("%s",str+1);
140 for (i=1;i<=n;i++)
141 {
142 if (str[i]=='r')
143 a[i]=0;
144 else if (str[i]=='s')
145 a[i]=1;
146 else
147 a[i]=2;
148 }
149
150 scanf("%s",str+1);
151 for (i=1;i<=n;i++)
152 {
153 if (str[i]=='r')
154 b[i]=0;
155 else if (str[i]=='s')
156 b[i]=1;
157 else
158 b[i]=2;
159 }
160
161 get_result();
162 }
163
164 return 0;
165 }
166 /*
167 3
168 rrr
169 sss
170
171 ======
172
173
174
175
176
177 10
178 sppsrrppsr
179 spsrsrsprr
180
181 ------
182 4
183
184
185 ======
186
187 10
188 rssrrpspss
189 ssrrprpppr
190
191 ------
192 6
193
194
195 ======
196
197 10
198 rssspsspps
199 psprrrrrrs
200
201 ------
202 5
203
204
205 ======
206
207 10
208 rpsrssrrrp
209 srsrrppsrs
210
211 ------
212 5
213
214
215 ======
216
217 10
218 prpprrpsps
219 ssrppprrsp
220
221 ------
222 4
223
224
225 ======
226
227 10
228 rspsssssrp
229 rsrsspsrrr
230
231 ------
232 3
233
234
235 ======
236
237 10
238 spsspssrrs
239 pspsprsrrs
240
241 ------
242 4
243
244
245 ======
246
247 10
248 prpprpsrps
249 rpspsrpsrp
250
251 ------
252 7
253
254
255 ======
256
257 10
258 sssprrspps
259 rprssssspr
260
261 ------
262 4
263
264
265 ======
266
267 10
268 rrsprsrspp
269 prrsrssrrr
270
271 ------
272 4
273
274
275 ======
276
277
278
279
280
281
282
283 6
284 sspspp
285 prssss
286
287 ------
288 1
289
290
291 ======
292
293 6
294 srssrp
295 srpssr
296
297 ------
298 3
299
300
301 ======
302
303 6
304 rpppsp
305 rppsrs
306
307 ------
308 2
309
310
311 ======
312
313 6
314 rpppsp
315 rprrpr
316
317 ------
318 4
319
320
321 ======
322
323 6
324 ssrpps
325 rpssps
326
327 ------
328 2
329
330
331 ======
332
333 6
334 pssrss
335 rrsppr
336
337 ------
338 3
339
340
341 ======
342
343 6
344 prrsps
345 sspssp
346
347 ------
348 2
349
350
351 ======
352
353 6
354 ppppsr
355 sprsrp
356
357 ------
358 2
359
360
361 ======
362
363 6
364 sppsss
365 rpsrrs
366
367 ------
368 1
369
370
371 ======
372
373 6
374 pprspr
375 psrrss
376
377 ------
378 2
379
380
381 ======
382
383
384
385
386
387
388
389
390 */
标签：10,const,int,LL,cf,dev,Metacamp2022,maxn,long From： https://www.cnblogs.com/cmyg/p/18157238