如何把你的50ptsDP优化到100pts（xyd夏令营7.28模考T3）

· · 休闲·娱乐

我们充分发扬人类智慧，将DP的第二维设置成符合时空限制的数

题面

3. 旋转(rotate)

时间限制: 1000ms

空间限制: 262144kB

题目描述

输入格式

输出格式

样例

Input 1

5
1 1 0 3 3
2 2 0 0 0

Output 1

2
数据范围

附件

rotate5.zip

代码

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int n,a[N];
int dp[N][505];

int main()
{
    scanf("%d",&n);
    const int m=n<=100?n*3:sqrt(2e7/n);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    for(int i=1,x;i<=n;i++)scanf("%d",&x),a[i]=(x-a[i]+4)%4;
    memset(dp,0x3f,sizeof(dp));
    dp[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            int x=j;
            if(x%4!=a[i])x+=(a[i]-x%4+4)%4;
            for(int k=0;k<=m;k++)
            {
                dp[i][j]=min(dp[i][j],dp[i-1][k]+max(0,x-k));
            }
        }
    }
    printf("%d",dp[n][0]);
    return 0;
}