绍兴一中模拟赛3.21——孰是孰非

绍兴一中模拟赛3.21——孰是孰非

Description

有一个长为 n ( n ≤ 500 ) n(n≤500) n(n≤500)的序列，每次可以选一段区间加上 x x x，如果有数大于 7 7 7就减 7 7 7（保持所有数 ∈ [ 1 , 7 ] ∈[1,7] ∈[1,7]）
问：最少几次这样的操作才能使所有 a i a_i ai​都等于 7 7 7

Solution

s t e p 1 ： step1： step1：先差分一下，令 b i = a i − a i − 1 ( 1 ≤ i ≤ n + 1 , a 0 = a n + 1 = 0 ) b_i=a_i-a_{i-1}(1≤i≤n+1,a_0=a_{n+1}=0) bi​=ai​−ai−1​(1≤i≤n+1,a0​=an+1​=0)
每次操作就变成 b l + x b_l+x bl​+x， b r + 1 − x b_{r+1}-x br+1​−x，目的是让所有 b i = 0 b_i=0 bi​=0
s t e p 2 ： step2： step2：我们发现 1 1 1和 6 6 6是可以一次抵消掉的，同理， 2 2 2和 5 5 5、 3 3 3和 4 4 4也一样
暴力消的话，也最多消数的个数次就行
s t e p 3 ： d p step3：dp step3：dp
因为 1 1 1和 6 6 6、 2 2 2和 5 5 5、 3 3 3和 4 4 4每对都有一个数被抵消掉了，所以 d p dp dp状态只要四维就行（第四维是记录当前这些数的和）
设 f [ i ] [ j ] [ k ] [ l ] f[i][j][k][l] f[i][j][k][l]表示已经用了 i i i个 1 / 6 1/6 1/6， j j j个 2 / 5 2/5 2/5， k k k个 3 / 4 3/4 3/4，总和 m o d 7 mod7 mod7为 l l l时，最多能少几个步骤，转移见代码
复杂度 O ( 7 ⋅ ( n 6 ) 3 ) O(7cdot(frac{n}{6})^3) O(7⋅(6n​)3)

Code

#include<bits/stdc++.h>
using namespace std;
int n,x,y,z,i,mx,my,mz,l,j,k,a[8],f[2][502][502][7],las,ans,p;
void Max(int &x,int y){if(y>x)x=y;}
int main(){scanf("%d",&n);for (i=1;i<=n;i++){scanf("%d",&x);a[(x-las+7)%7]++,las=x;}a[7-las]++;if (a[1]>a[6]) x=1,swap(a[1],a[6]);else x=6;if (a[2]>a[5]) y=2,swap(a[2],a[5]);else y=5;if (a[3]>a[4]) z=3,swap(a[3],a[4]);else z=4;ans=a[4]+a[5]+a[6];mx=a[6]-a[1],my=a[5]-a[2],mz=a[4]-a[3];for (i=0;i<=mx;i++,p^=1)for (j=0;j<=my;j++)for (k=0;k<=mz;k++)for (l=0;l<7;l++)Max(f[p^1][j][k][(l+x)%7],f[p][j][k][l]+(l+x==7)),Max(f[p][j+1][k][(l+y)%7],f[p][j][k][l]+(l+y==7)),Max(f[p][j][k+1][(l+z)%7],f[p][j][k][l]+(l+z==7));printf("%d",ans-f[p^1][my][mz][0]);
}