题解 P11838

题目：P11838 [USACO25FEB] Printing Sequences B - 洛谷

赛场上很自然想到的是区间 DP。

定义 $dp[l][r]$ 为区间 $[l, r]$ 内最少使用 PRINT 语句的次数。考虑转移，在 $[l, r]$ 内枚举 $m$，若 $[l, r]$ 区间可以由 $[l, m]$ 循环得到，就把 $[l, m]$ 的答案转移给 $[l, r]$。如果不可以就把两个区间 $[l, m]$ 与 $[m+1,r]$ 答案相加。

转移方程如下：

$$
dp[l][r]=
\begin{cases}
dp[l][m]+dp[m+1][r] & \text{任意情况} \
dp[l][p] & [l, r] \text{可由若干个} [l, p] \text{循环得到}
\end{cases}
$$

常数不是很大，直接暴力循环判断是否满足即可。时间复杂度 $O(T \times n^4)$。

慢着，似乎哪里有问题？这个复杂度能过？

对于任意情况的转移是 $O(T \times n^3)$。把视线放到暴力判断那一块，不难发现，在枚举 $p$ 的时候并不用循环处理每一位，可以判断 $(p-l+1) \mid len$ 是否成立，若不成立则说明 $[l, r]$ 不可由若干个 $[l, p]$ 循环得到，直接跳出循环。$len$ 的约数个数肯定是严格小于 $2 \sqrt{len}$ 的（貌似高了许多），最简单的质数筛的写法就可以证明。这样看总复杂度（最坏）就是 $O(T \times n^3 \sqrt{n})$。循环判断不符合很快也会跳出循环。$10^2$ 绰绰有余（逃）

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
void solve();
void fac();
signed main(){
    ios::sync_with_stdio(false);
    int _=read();
    while(_--) solve();
    return 0;
}
const int N=2e3+10;
int n,K;
int val[N];
int dp[N][N];
void solve(){
    memset(dp,0x3f,sizeof(dp)); 
    n=read(),K=read();
    for(int i=1;i<=n;i++) val[i]=read();
    for(int i=1;i<=n;i++) dp[i][i]=1;
    for(int len=2;len<=n;len++){
        for(int l=1;l<=n;l++){
            int r=l+len-1; if(r>n) continue;
            for(int m=l;m<r;m++){
                dp[l][r]=min(dp[l][r],dp[l][m]+dp[m+1][r]);
            }
            for(int p=1;p<=len;p++){
                if(len%p!=0) continue;
                bool rr=true;
                for(int pos=l;pos<=r;pos++) if(val[pos]!=val[l+(pos-l)%p]){
                    rr=false; break;
                }
                if(rr) dp[l][r]=min(dp[l][r],dp[l][l+p-1]);
            }
        }
    }
    cout<<((dp[1][n]<=K)?"YES":"NO")<<"\n";
    return;
}