CodeForces-796E Exam Cheating 【DP】

제목 링크

제목의 뜻

두 개의 축에 약간의 정수(n<100)가 있는데, p개(p<100)개의 길이가 k(k<=50)보다 작은 구간으로 이 정수를 덮어쓰고, 최대 몇 개의 정수가 덮어쓸 수 있는지 구하라(같은 중복 계수)

분석하다.

이 4차원 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\rac{n} {k}\rceil\)하면 dp를 뛸 필요가 없고, dp를 필요로 하는 경우는 최대 1000*1000*50이면 다 뛸 수 있다.

AC 코드

//CodeForces-796E Exam Cheating
//AC 2017-4-12 18:41:19 by Carl Luo
//DP
#include 
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<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<

전재 대상:https://www.cnblogs.com/DrCarlluo/p/6700799.html