题目链接：E. Exam Cheating 题意是有个女同学要作弊，总共有n道题，旁白有两位学霸，但是他们分别完成了r道题和s道题（按题号严格递增）。这位同学要作弊总共能看p次，每次只能看一位同学的最多连续k道题，只有学霸完成了的题目才能看。问最多能看多少道题。
感觉很巧妙的dp题，一开始我以两位学霸完成了题目为时间轴，但是后来发现有相互覆盖的情形。看了别人的状态后，是这样的：以题目为时间轴，dp[i][a][b][x]代表前i道题看了x眼且第一个学霸还剩下a道题，第二个学霸剩下b道题可以看。 解释一下a b 这个状态吧，我也是看挺久才理解的。 以第一个样例为例 6 2 3 3 1 3 6 4 1 2 5 6 总共有 1 2 3 4 5 6 六道题（加粗代表学霸已经完成的题目） 第一个1 2 3 4 5 6 第二个1 2 3 4 5 6 那么由于每次能最多看连续k个题，毫无疑问我们肯定就看k个题 于是假设在第二题处看了第二个人一眼 状态就是dp[2][0][2][1] ，除去了当前看这道题，对于第二个人我们还能往后面再看2个题 假设在第一道题处看了第一个人一眼，那么就是dp[1][2][0][1] 然后说一下转移，由于每次可以选择看或者不看 假设不看 dp[i][a][b][x] = max(dp[i-1][a+1][b+1][x] , dp[i][a][b][x]) 如果看呢 比如看了第一个人，那么第一个人肯定还会剩下k-1道题可以看。 dp[i][k-1][b][x] = max(dp[i][a][b][x] , dp[i-1][a][b+1][x - 1]) 看了第二个人也同理 还有就是当a b 等于0的时候要特殊处理，a b等于0的时候仍然可以转移，但是方程就要变动一下了由于比较复杂直接贴代码吧 数据范围比较大避免MLE就用滚动数组来代替
#include<cmath> #include<algorithm> #include<cstring> #include<string> #include<set> #include<map> #include<time.h> #include<cstdio> #include<vector> #include<list> #include<stack> #include<queue> #include<iostream> #include<stdlib.h> using namespace std; #define LONG long long const int INF=0x3f3f3f3f; const LONG MOD=1e9+ 7; const double PI=acos(-1.0); #define clrI(x) memset(x,-1,sizeof(x)) #define clr0(x) memset(x,0,sizeof x) #define clr1(x) memset(x,INF,sizeof x) #define clr2(x) memset(x,-INF,sizeof x) #define EPS 1e-10 #define lson l , mid , rt<< 1 #define rson mid + 1 ,r , (rt<<1)+1 #define root 1, m , 1 int A[5010] ; int B[5010] ; int dp[2][55][55][500] ; int ab(int x) { if(x < 0 )return 0 ; return x; } int Cei(int a , int b) { if(a % b != 0) return a/b + 1; return a / b; } int main() { int n , p , k ; clr0( A ) ; clr0( B ) ; clr2( dp ) ; cin >> n >> p >>k ; if( p > 2 * Cei(n , k) ) p =2 * Cei(n,k) ; int xx ; int tt ; cin >> tt ; for(int i = 1 ; i <= tt ;++i) cin >> xx , A[xx] = 1 ; cin >> tt ; for(int i = 1 ; i <= tt ; ++ i) cin >> xx , B[xx] = 1 ; int pre = 0 , now = 1; dp[0][0][0][0] = 0 ; int ans = 0 ; for(int i = 1 ; i <= n ; ++ i) { for(int x = 0 ; x <= p ; ++ x) { for(int a = 0 ; a <= k - 1 ; ++ a) { for(int b = 0 ; b <= k - 1 ; ++ b) { if(b != 0 && a== 0) { dp[now][k-1][(b-1)][x +1] = max(dp[now][k-1][(b-1)][x+1], dp[pre][a][b][x] + (A[i] | B[i]) ); dp[now][a][b-1][x] = max(dp[now][a][b-1][x] , dp[pre][a][b][x] + B[i]) ; dp[now][a][k-1][x+1] = max(dp[now][a][k-1][x+1] , dp[pre][a][b][x] + B[i]) ; } else if( b == 0 && a == 0) { dp[now][k-1][b][x+1] = max(dp[now][k-1][b][x+1] , dp[pre][a][b][x] + A[i] ) ; dp[now][a][b][x] = max(dp[now][a][b][x] , dp[pre][a][b][x] ) ; dp[now][a][k-1][x+1] = max(dp[now][a][k-1][x+1] , dp[pre][a][b][x] + B[i] ) ; } else if(a != 0 && b != 0) { dp[now][(a-1)][ k - 1][x +1] = max(dp[now][(a - 1)][k-1][x+1], dp[pre][a][b][x] + ((A[i]) || (B[i]))); dp[now][a-1][b-1][x] = max(dp[now][a-1][b-1][x] , dp[pre][a][b][x] + (A[i] || B[i])) ; dp[now][k-1][b-1][x+1] = max(dp[now][k-1][b-1][x+1] , dp[pre][a][b][x] + ( A[i] || B[i]) ) ; } else if(a!= 0 && b == 0) { dp[now][a-1][b][x] = max(dp[now][a-1][b][x] , dp[pre][a][b][x] + A[i]) ; dp[now][a-1][k- 1][x+1] = max(dp[now][a-1][k-1][x+1] , dp[pre][a][b][x] + (A[i] | B[i])) ; dp[now][k-1][b][x + 1] = max(dp[now][k-1][b][x+1] , dp[pre][a][b][x] + A[i] ) ; } } } } clr2(dp[pre]) ; now ^= 1 ; pre ^= 1; } for(int i = 0 ; i <= p ; ++ i) { for(int a = 0 ; a <= k ; ++ a) for(int b = 0 ; b <= k ; ++ b)ans = max(ans , dp[pre][a][b][i]) ; } cout<<ans <<endl; }