题意
在两个数轴上有一些整数（n<1000），用p个（p<1000）个长度小于等于k（k<=50）的区间去覆盖这些整数，求最多多少个整数能够被覆盖（相同的不重复计数）
分析
易想到这个四维DP的状态：
[dp[n][p][r1][r2] leftrightarrow 到n用了p个区间，上面覆盖的最后一个区间的长度为r1，下面的覆盖的最后一个区间的长度为r2
]
直接开这个数组，1000*1000*50*50会炸，通过下面的转移方程可以发现对n可以滚动数组优化。
至于转移方程就比较麻烦了，主要是考虑三种情况：
- 直接在前两个区间后面再加一个
- 新开一个区间
- 新开两个区间
具体如何转移可以看下面的代码（可能写得比较繁琐，然而我觉得标程比我写得还繁琐），其中新开区间需要记录上一个位置的最大值，同样注意通过记录最大值来优化。
这样之后仍然无法再2s内跑完（(O(npk^2)) 2e9的复杂度）这里需要一个特别的优化：如果区间多到可以将n以内的每个数都能覆盖，则直接(O(n))就可以算出答案。也就是说，如果(p>lceil frac{n}{k} ceil)就不需要跑dp了，而剩下需要dp的情况最多为1000*1000*50就可以跑完
AC代码
//CodeForces-796E Exam Cheating
//AC 2017-4-12 18:41:19 by Carl Luo
//DP
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e3+100;
int n,p,k;
int dp[2][maxn][55][55];
int maks[2][2][maxn][55];
int tmaks[2][maxn];
int question[2][maxn];
int main()
{
scanf("%d %d %d",&n,&p,&k);
int cnt,x;
int res=0;
for(int i=0;i<2;++i)
{
scanf("%d",&cnt);
while(cnt--)
{
scanf("%d",&x);
question[i][x]=1;
}
}
if(p>2*ceil(n/k))
{
for(int i=1;i<=n;++i)
res+=(question[0][i]||question[1][i]);
cout<<res<<endl;
return 0;
}
int now=0;
memset(dp,0xc0,sizeof dp);
//dp[1][0][0][0]=0;
memset(maks,0xc0,sizeof maks);
memset(tmaks,0xc0,sizeof tmaks);
maks[1][0][0][0]=maks[1][1][0][0]=tmaks[1][0]=0;
for(int i=1;i<=n;++i)
{
//cout<<i<<"!!!!!!!!!!!!!!!!!"<<endl;
for(int j=0;j<=p;++j)
{
tmaks[now][j]=-0x3f3f3f3f;
for(int r=0;r<=k;++r)
{
maks[now][0][j][r]=maks[now][1][j][r]=-0x3f3f3f3f;
for(int r1=0;r1<=k;++r1)
dp[now][j][r][r1]=-0x3f3f3f3f;
}
}
for(int j=0;j<=p;++j)
{
//cout<<j<<endl;
for(int r1=0;r1<=k;++r1)
{
for(int r2=0;r2<=k;++r2)
{
int &cur=dp[now][j][r1][r2];
if(r1>1&&r2>1&&j>=2)
cur=max(cur,dp[!now][j][r1-1][r2-1]+(question[0][i]||question[1][i]));
if((r1==0||r1==1)&&j>=r1&&!(r2==0||r2==1))
cur=max(cur,maks[!now][0][j-r1][r2-1]+(question[1][i]||(question[0][i]&&r1)));
if((r2==0||r2==1)&&j>=r2&&!(r1==0||r1==1))
cur=max(cur,maks[!now][1][j-r2][r1-1]+((question[1][i]&&r2)||question[0][i]));
if((r1==0||r1==1)&&(r2==0||r2==1)&&j>=r1+r2)
cur=max(cur,tmaks[!now][j-r1-r2]+((question[0][i]&&r1)||(question[1][i]&&r2)));
//cout<<cur<<" ";
tmaks[now][j]=max(tmaks[now][j],cur);
maks[now][0][j][r2]=max(maks[now][0][j][r2],cur);
maks[now][1][j][r1]=max(maks[now][1][j][r1],cur);
res=max(res,cur);
}
//cout<<endl;
}
//cout<<"---------------------"<<endl;
}
now=!now;
}
printf("%d
",res);
}