【原題】

【題目翻譯】

KajKeusaka是個(gè)學(xué)渣，考試的時(shí)候，他一道題也不會(huì)做

他的左右桌分別是學(xué)霸ModestCoder和學(xué)霸Dawn_Chase，雖然學(xué)霸并不是題題都會(huì)做，但他們做了的題一定都對(duì)

現(xiàn)在KajKeusaka想要作弊，但是為了不被監(jiān)考員抓住，他最多偷看p次，一次能看連續(xù)的k道題

給定n和la和lb，分別為題目總數(shù)，ModestCoder做出題目數(shù)和Dawn_Chase做出題目數(shù)，再給出兩位學(xué)霸做出題目序列，問KajKeusaka最多能偷看到幾道題的答案

【輸入格式】

第一行三個(gè)整數(shù)n,p,k(1<=n,p<=1,000 , 1<=k<=min(n,50) )表示有n道題，KajKeusaka可以偷看p次，每次最多看k道題
第二行有一個(gè)整數(shù)la，表示ModestCoder做出的題數(shù)，接下來la個(gè)整數(shù)表示題號(hào)
第三行有一個(gè)整數(shù)lb，表示Dawn_Chase做出的題數(shù)，接下來lb個(gè)整數(shù)表示題號(hào)

【輸出格式】

一個(gè)整數(shù)表示KajKeusaka最多能偷看到幾題答案

$SampleInput$

6 2 3
3 1 3 6
4 1 2 5 6

$SampleOutput$

4

【題意分析】

一道巧妙dp，當(dāng)然我自己想不出

令$dp[i][j][L][R]$表示第$i$道題，已經(jīng)偷看了$j$次，ModestCoder還可以看$L$題，Dawn_Chase還可以看$R$題時(shí)最多能偷看到的題數(shù)

刷表討論：

• 兩個(gè)人都不偷看
• 偷看ModestCoder，可以接著上次看下去，也可以用一次次數(shù)重新開始看
• 偷看Dawn_Chase，同上
• 兩人都看，可以(ModestCoder/Dawn_Chase)重新看/重新看，接著看/接著看，接著看/重新看，重新看/接著看

兩人做出的題目用布爾型存起來方便提取
枚舉$i,j,L,R$
先是繼承上次的狀態(tài)$dp[i?1][j][L?1][R?1]$，用$res$存起來
為什么？因?yàn)榫退隳悴豢?#xff0c;題目還是會(huì)下去，L和R都是要減的
fix(x,y)是將x更新（如果y更大）

$$if(L)fix(dp[i][j][L?1][max(R?1,0)],res+a[I]);$$

如果左邊可以看，不用花費(fèi)次數(shù)直接更新，注意R-1不要越界

$$fix(dp[i][j+1][k?1][max(R?1,0)],res+a[I]);$$

左邊不管可不可以看，直接重新開始看，這要花費(fèi)一次次數(shù)，并且左邊剩余次數(shù)重置為k-1

$$if(L)fix(dp[i][j+1][L?1][k?1],res+(a[I]|b[I]));$$

如果左邊可以看，繼承左邊，重置右邊，花費(fèi)一次次數(shù)。$a[I]|b[I]$是表示兩邊都看能不能成功看到答案

$$fix(dp[i][j+2][k?1][k?1],res+(a[I]|b[I]));$$

不管兩邊能不能看，暴力重置，花費(fèi)兩次次數(shù)

$$if(LandR)fix(dp[i][j][L?1][R?1],res+(a[I]|b[I]));$$

如果兩邊都可以看，再好不過，不需要花費(fèi)次數(shù)

再算上右邊的鏡像模式，這樣我們就轉(zhuǎn)移完了，$ans$就是所有情況打擂臺(tái)

但是這樣會(huì)mle，發(fā)現(xiàn)$i$這維完全可以滾動(dòng)掉。

還有tle的風(fēng)險(xiǎn)，但是如果$p?k>=n?2$，那么就全部偷看唄，不看白不看，直接兩邊每次都看，特判輸出。

Code:

#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <algorithm> #define rep(x,a,b) for (register int x = a; x <= b; x++) #define MAXN 1005 #define MAXM 60 using namespace std;int dp[2][MAXN][MAXM][MAXM], a[MAXN], b[MAXN], n, m, k, l, r, ans;inline void fix (int &a, int b) {a = max (a, b);}inline int read () {register int s = 0, w = 1;register char ch = getchar ();while (! isdigit (ch)) {if (ch == '-') w = -1; ch = getchar ();}while (isdigit (ch)) {s = (s << 3) + (s << 1) + (ch ^ 48); ch = getchar ();}return s * w; }int main () {n = read (), m = read (), k = read ();l = read (); rep (i, 1, l) a[read ()] = 1;r = read (); rep (i, 1, r) b[read ()] = 1;if (m * k >= n * 2) {rep (i, 1, n) ans += a[i] | b[i];printf ("%d\n", ans); return 0;}memset (dp, -0x3f3f3f, sizeof dp), dp[0][0][0][0] = 0;rep (I, 1, n) {int i = I % 2, last = (I + 1) % 2;memset (dp[i], -0x3f3f3f, sizeof dp[i]);rep (j, 0, m) rep (L, 0, k) rep (R, 0, k) {int res = dp[last][j][L][R];fix (dp[i][j][max (L - 1, 0)][max (R - 1, 0)], res);if (L) fix (dp[i][j][L - 1][max (R - 1, 0)], res + a[I]);if (L) fix (dp[i][j + 1][L - 1][k - 1], res + (a[I] | b[I]));if (R) fix (dp[i][j][max (L - 1, 0)][R - 1], res + b[I]);if (R) fix (dp[i][j + 1][k - 1][R - 1], res + (a[I] | b[I]));if (L && R) fix (dp[i][j][L - 1][R - 1], res + (a[I] | b[I]));fix (dp[i][j + 1][k - 1][max (R - 1, 0)], res + a[I]);fix (dp[i][j + 1][max (L - 1, 0)][k - 1], res + b[I]);fix (dp[i][j + 2][k - 1][k - 1], res + (a[I] | b[I]));}}rep (j, 0, m) rep (L, 0, k) rep (R, 0, k) fix (ans, dp[n % 2][j][L][R]);printf ("%d\n", ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的[CF796E Round#408 Div.2]Exam Cheating——[计数DP]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。