2018-2019 ICPC Southwestern European Regional Programming Contest (SWERC 2018) 补题记录（9 / 11）

发表于 更新于 分类于 本文字数： 16k 阅读时长 ≈ 15 分钟

SWERC 2018 补题记录

A. City of Lights

tag

  • 模拟

题意

共 nn 盏灯，编号 1−n1 - n ， kk 次操作每次开/关编号是 kk 的倍数的灯，求过程中最多同时熄灭的灯数。
其中 1≤n≤106,1≤k≤1001 \leq n \leq 10^6, 1 \leq k \leq 100 。

思路

模拟即可。
复杂度 O(n⋅k)O(n \cdot k) 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*
    Author: Cupids_Bow
    Time: 2022-09-29 08:57:14
*/
#include<bits/stdc++.h>
using namespace std;

using ll=long long;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n,k;
    cin>>n>>k;

    vector<int> vis(n+1,0);
    int cnt=0,ans=0;
    for(int i=0,x;i<k;i++){
        cin>>x;
        for(int i=x;i<=n;i+=x){
            cnt-=vis[i];
            vis[i]^=1;
            cnt+=vis[i];
        }
        ans=max(ans,cnt);
    }

    cout<<ans;

    return true&&false;
}

B. Blurred Pictures

tag

  • 模拟
  • 双指针

题意

n⋅nn \cdot n 的网格0，第 ii 行 [li,ri][l_i, r_i] 内是 11 ，其余是 00 ，求最大的只含 11 的正方形。
其中 1≤n≤1051 \leq n \leq 10^5 。

思路

枚举正方形所在行的右端点 ii ，易发现左端点有单调性，双指针 + setset 维护即可。
复杂度 O(n⋅logn)O(n \cdot logn) 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*
    Author: Cupids_Bow
    Time: 2022-09-29 09:22:19
*/
#include<bits/stdc++.h>
using namespace std;

using ll=long long;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n;
    cin>>n;

    vector<array<int,2>> vec(n);
    for(auto &[l,r]:vec) cin>>l>>r;

    multiset<int> stmi,stmx;
    int p=0,ans=0;
    for(int i=0;i<n;i++){
        auto [l,r]=vec[i];
        stmi.insert(r);
        stmx.insert(l);
        while(p<=i&&(*stmi.begin())-(*stmx.rbegin())+1<i-p+1){
            auto [L,R]=vec[p];
            stmi.erase(stmi.find(R));
            stmx.erase(stmx.find(L));
            p++;
        }
        ans=max(ans,min(i-p+1,(*stmi.begin())-(*stmx.rbegin())+1));
    }

    cout<<ans;

    return true&&false;
}

D. Monument Tour

tag

  • 数学

题意

X⋅YX \cdot Y 的网格，选一条平行 XX 轴的路线使得按给定路线经过每个观光点的路程总和最小。
其中 1≤X,Y≤1051 \leq X, Y \leq 10^5 。

思路

XX 相同的观光点只需要记录 YY 的最大值和最小值。相当于计算若干条线段的贡献，枚举 YY 即可。
复杂度 O(n+X+Y)O(n + X + Y) 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/*
    Author: Cupids_Bow
    Time: 2022-09-29 09:06:40
*/
#include<bits/stdc++.h>
using namespace std;

using ll=long long;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int X,Y;
    cin>>X>>Y;

    int n;
    cin>>n;

    vector<int> mx(X,-1),mi(X,Y+1);
    for(int i=0,x,y;i<n;i++){
        cin>>x>>y;
        mx[x]=max(mx[x],y);
        mi[x]=min(mi[x],y);
    }

    ll sum=0;
    ll cntl=0,cntr=0;
    ll suml=0,sumr=0;
    vector<int> L(Y,0),R(Y,0);
    for(int i=0;i<X;i++) if(mx[i]!=-1){
        L[mi[i]]++;
        R[mx[i]]++;
        sum+=2ll*(mx[i]-mi[i]);
        cntl++;
        suml+=mi[i];
    }

    ll ans=0x3f3f3f3f3f3f3f3f;
    for(int i=0;i<Y;i++){
        cntl-=L[i];
        cntr+=R[i];
        suml-=1ll*L[i]*i;
        sumr+=1ll*R[i]*i;
        ans=min(ans,sum+(2ll*i*cntr-2ll*sumr)+(2ll*suml-2ll*i*cntl));
    }
    ans+=X-1;

    cout<<ans;

    return true&&false;
}

E. Rounding

tag

  • 数学

题意

给定 nn 个数四舍五入后的值，求每个数原来可能的范围（二位小数），无解输出 IMPOSSIBLEIMPOSSIBLE ，要求原来的数总和为 100100 。
其中 1≤n≤1041 \leq n \leq 10^4 。

思路

枚举每个数原来可能的值，判断合不合法即可。
复杂度 O(n⋅100)O(n \cdot 100) 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/*
    Author: Cupids_Bow
    Time: 2022-09-29 10:00:09
*/
#include<bits/stdc++.h>
using namespace std;

using ll=long long;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n;
    cin>>n;

    vector<string> name(n);
    vector<int> a(n);
    int tot=0;
    for(int i=0;i<n;i++){
        cin>>name[i]>>a[i],a[i]*=100;
        tot+=a[i];
    }

    vector<int> lans(n),rans(n);
    for(int i=0;i<n;i++){
        lans[i]=10001;
        rans[i]=-1;
    }
    for(int i=0;i<n;i++){
        auto check=[&](int val,int id){
            int l=tot-a[i],
                r=tot-a[i];
            l-=50*(n-1);
            r+=49*(n-1);
            int sum=10000-val;
            if(l<=sum&&sum<=r) return 1;
            return 0;
        };

        for(int j=max(a[i]-50,0);j<=min(a[i]+49,10000);j++) if(check(j,i)){
            lans[i]=min(lans[i],j);
            rans[i]=max(rans[i],j);
        }
    }

    if(lans[0]==10001) cout<<"IMPOSSIBLE";
    else{
        for(int i=0;i<n;i++){
            cout<<name[i]<<" ";
            cout<<lans[i]/100<<".";
            cout<<fixed<<setfill('0')<<setw(2)<<lans[i]%100<<" ";
            cout<<rans[i]/100<<".";
            cout<<fixed<<setfill('0')<<setw(2)<<rans[i]%100<<"\n";
        }
    }

    return true&&false;
}

F. Paris by Night

tag

  • 计算几何
  • 双指针

题意

nn 个二维平面的点，选两个点做直线，贡献为直线两端的点的价值和之差，最小化这个差的绝对值。
其中 1≤n≤4⋅1031 \leq n \leq 4 \cdot 10^3 。

思路

枚举直线上的一个点 pp ，剩余点按 pp 极角排序，分布在直线一侧的点可以双指针维护，过程中取 minmin 即可。
复杂度 O(n2⋅logn)O(n^2 \cdot logn) 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
/*
    Author: Cupids_Bow
    Time: 2022-09-29 11:12:36
*/
#include<bits/stdc++.h>
using namespace std;

using ll=long long;

const double eps=1e-8;
const double inf=1e20;
const double pi=acos(-1.0);
const int maxp=4e3+5;

int sgn(double x){
    if(fabs(x)<eps) return 0;
    if(x<0) return -1;
    else return 1;
}

inline double sqr(double x){return x*x;}

struct Point{
    double x,y;
    ll w;
    Point(double _x=0,double _y=0,ll _w=0){
        x=_x;
        y=_y;
        w=_w;
    }
    void input(){
        cin>>x>>y>>w;
    }
    void output(){
        cout<<x<<" "<<y<<" "<<w<<"\n";
    }
    bool operator == (Point b)const{
        return sgn(x-b.x)==0&&sgn(y-b.y)==0;
    }
    bool operator < (Point b)const{
        return sgn(x-b.x)==0?sgn(y-b.y)<0:x<b.x;
    }
    Point operator - (const Point &b)const{
        return Point(x-b.x,y-b.y);
    }
    double operator ^ (const Point &b)const{
        return x*b.y-y*b.x;
    }
    double operator * (const Point &b)const{
        return x*b.x+y*b.y;
    }
    double len(){
        return hypot(x,y);
    }
    double len2(){
        return x*x+y*y;
    }
    double distance(Point p){
        return hypot(x-p.x,y-p.y);
    }
    Point operator + (const Point &b)const{
        return Point(x+b.x,y+b.y);
    }
    Point operator * (const double &k)const{
        return Point(x*k,y*k);
    }
    Point operator / (const double &k)const{
        return Point(x/k,y/k);
    }
    double rad(Point a,Point b){
        Point p=*this;
        return fabs(atan2(fabs((a-p)^(b-p)),(a-p)*(b-p)));
    }
    Point trunc(double r){
        double l=len();
        if(!sgn(l)) return *this;
        r/=l;
        return Point(x*r,y*r);
    }
    Point rotleft(){
        return Point(-y,x);
    }
    Point rotright(){
        return Point(y,-x);
    }
    Point rotate(Point p,double angle){
        Point v=(*this)-p;
        double c=cos(angle),s=sin(angle);
        return Point(p.x+v.x*c-v.y*s,p.y+v.x*s+v.y*c);
    }
};

int n;
Point p[maxp];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n;
    if(n==2){
        cout<<"0";
        return true&&false;
    }

    ll tot=0;
    for(int i=0;i<n;i++) p[i].input(),tot+=p[i].w;

    auto calc=[&](int id){
        vector<Point> vec;
        for(int i=0;i<n;i++) if(i!=id) vec.push_back(p[i]);

        auto get_area=[&](Point &a){
            auto [x,y,w]=a;
            if(x==0&&y>=0) return 0;
            else if(x>0&&y>0) return 1;
            else if(x>0&&y==0) return 2;
            else if(x>0&&y<0) return 3;
            else if(x==0&&y<0) return 4;
            else if(x<0&&y<0) return 5;
            else if(x<0&&y==0) return 6;
            else return 7;
        };

        sort(vec.begin(),vec.end(),[&](const Point &a,const Point &b){
            Point p1=a-p[id];
            Point p2=b-p[id];
            int area1=get_area(p1);
            int area2=get_area(p2);
            if(area1!=area2) return area1<area2;
            else return (p1^p2)<0;
        });

        for(int i=0;i<n-1;i++) vec.push_back(vec[i]);

        ll res=tot,sum=0;
        int r=-1;
        for(int i=0;i<n-1;i++){
            if(r<i){
                sum=vec[i].w;
                r=i;
            }
            while(r+1<vec.size()&&r+1<i+n-1&&sgn((vec[i]-p[id])^(vec[r+1]-p[id]))<=0){
                r++;
                sum+=vec[r].w;
            }
            sum-=vec[i].w;
            res=min(res,abs(tot-p[id].w-vec[i].w-2*sum));
        }

        return res;
    };

    ll ans=tot;
    for(int i=0;i<n;i++) ans=min(ans,calc(i));

    cout<<ans;

    return true&&false;
}

G. Strings

tag

  • 搜索

题意

初始串 s0s_0 ， n−1n - 1 次操作，第 ii 次操作可以：

  • SUB x l rSUB\ x\ l\ r ，取 sxs_x 的子串 sx[l,r]s_x[l, r] 作为 sis_i
  • APP x yAPP\ x\ y ，取 sx+sys_x + s_y 作为 sis_i

求 sn−1s_{n - 1} 的所有字符的 ASCIIASCII 码之和，模 109+710^9 + 7 。
其中 1≤n≤2500,1≤∣s0∣≤10001 \leq n \leq 2500, 1 \leq |s_0| \leq 1000 。

思路

从 sn−1s_{n - 1} 开始记忆化搜索即可。
复杂度 O(n2)O(n^2) 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/*
    Author: Cupids_Bow
    Time: 2022-09-29 20:08:56
*/
#include<bits/stdc++.h>
using namespace std;

using int64=long long;
using uint64=unsigned long long;

const int mod=1e9+7;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n;
    cin>>n;

    string s;
    cin>>s;

    vector<array<int64,3>> op(n);
    vector<uint64> len(n,0);
    len[0]=s.size();
    for(int i=1;i<n;i++){
        string str;
        cin>>str;
        if(str[0]=='S'){
            auto &[x,l,r]=op[i];
            cin>>x>>l>>r;
            len[i]=r-l;
        }
        else{
            auto &[u,x,y]=op[i];
            cin>>x>>y;
            u=-1;
            len[i]=len[x]+len[y];
        }
    }

    vector<map<uint64,int>> dp(n);
    function<int(int,int64)> calc=[&](int n,uint64 S){
        if(dp[n].count(S)) return dp[n][S];
        if(n==0){
            int res=0;
            for(int i=0;i<S;i++) res=(res+s[i])%mod;
            return dp[n][S]=res;
        }
        else if(op[n][0]==-1){
            auto [u,x,y]=op[n];
            if(S<=len[x]) return dp[n][S]=calc(x,S);
            else{
                int res=calc(x,len[x]);
                res=(res+calc(y,S-len[x]))%mod;
                return dp[n][S]=res;
            }
        }
        else{
            auto [x,l,r]=op[n];
            int res=calc(x,l+S);
            res=(res+mod-calc(x,l))%mod;
            return dp[n][S]=res;
        }
    };

    cout<<calc(n-1,len[n-1]);

    return true&&false;
}

H. Travel Guide

tag

  • 最短路
  • CDQ分治

题意

nn 个点 mm 条边的无向连通图，定义三元组 (dis0,i,dis1,i,dis2,i)(dis_{0,i},dis_{1,i},dis_{2,i}) ，其中 disi,jdis_{i,j} 表示点 i,ji, j 之间的最短路，求有多少个三元组 (xi,yi,zi)(x_i, y_i, z_i) 满足不存在 jj 使得 xj≤xi,yj≤yi,zj≤zix_j \leq x_i, y_j \leq y_i, z_j \leq z_i 且 (xi,yi,zi)(x_i, y_i, z_i) 与 (xj,yj,zj)(x_j, y_j, z_j) 不完全相同。
其中 0≤n≤105,n−1≤m≤5⋅1050 \leq n \leq 10^5, n - 1 \leq m \leq 5 \cdot 10^5 。

思路

对 0,1,20, 1, 2 三点跑分别最短路后套 cdqcdq 分治即可，注意三元组完全相等的情况。
复杂度 O(n⋅logn2)O(n \cdot logn^2) 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
/*
    Author: Cupids_Bow
    Time: 2022-09-29 13:20:37
*/
#include<bits/stdc++.h>
using namespace std;

using ll=long long;

const int INF=0x3f3f3f3f;

const int N=1e5+5;
struct BIT{
    int val[N];
    void add(int x,int k){
        for(int i=x;i<N;i+=(i&-i)) val[i]+=k;
    }
    int sum(int x){
        int res=0;
        for(int i=x;i;i-=(i&-i)) res+=val[i];
        return res;
    }
}bit;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n,m;
    cin>>n>>m;

    vector<vector<array<int,2>>> e(n,vector<array<int,2>>(0));
    for(int i=0,x,y,z;i<m;i++){
        cin>>x>>y>>z;
        e[x].push_back({y,z});
        e[y].push_back({x,z});
    }

    vector<int> dis(n,INF);
    auto dij=[&](int st){
        priority_queue<array<int,2>,vector<array<int,2>>,greater<array<int,2>>> q;
        for(int i=0;i<n;i++) dis[i]=INF;
        dis[st]=0;
        q.push({dis[st],st});
        while(!q.empty()){
            auto [d,x]=q.top();
            q.pop();
            if(d>dis[x]) continue;
            for(auto [v,w]:e[x]){
                if(dis[v]>dis[x]+w){
                    dis[v]=dis[x]+w;
                    q.push({dis[v],v});
                }
            }
        }
    };

    vector<array<int,3>> a(n);
    vector<int> app;
    map<array<int,3>,int> maxn,mp;
    dij(0);
    for(int i=0;i<n;i++) a[i][0]=dis[i];
    dij(1);
    for(int i=0;i<n;i++) a[i][1]=dis[i];
    dij(2);
    for(int i=0;i<n;i++){
        a[i][2]=dis[i];
        app.push_back(dis[i]);
    }
    sort(app.begin(),app.end());
    app.erase(unique(app.begin(),app.end()),app.end());
    for(int i=0;i<n;i++){
        a[i][2]=lower_bound(app.begin(),app.end(),a[i][2])-app.begin()+1;
        mp[a[i]]++;
    }

    vector<int> sum(n,0);
    vector<int> qry(n,0);
    iota(qry.begin(),qry.end(),0);
    function<void(int,int)> solve=[&](int l,int r){
        if(l==r) return;
        int mid=l+r>>1;
        solve(l,mid);
        solve(mid+1,r);
        int i=l,
            j=mid+1;
        vector<int> tmp(0);
        while(i<=mid&&j<=r){
            if(a[qry[i]][1]<=a[qry[j]][1]){
                bit.add(a[qry[i]][2],1);
                tmp.push_back(qry[i]);
                i++;
            }
            else{
                sum[qry[j]]+=bit.sum(a[qry[j]][2]);
                tmp.push_back(qry[j]);
                j++;
            }
        }
        while(i<=mid){
            bit.add(a[qry[i]][2],1);
            tmp.push_back(qry[i]);
            i++;
        }
        while(j<=r){
            sum[qry[j]]+=bit.sum(a[qry[j]][2]);
            tmp.push_back(qry[j]);
            j++;
        }
        for(int i=l;i<=mid;i++) bit.add(a[qry[i]][2],-1);
        for(int i=l;i<=r;i++) qry[i]=tmp[i-l];
    };

    sort(qry.begin(),qry.end(),[&](const int &x,const int &y){
        if(a[x][0]!=a[y][0]) return a[x][0]<a[y][0];
        else if(a[x][1]!=a[y][1]) return a[x][1]<a[y][1];
        else return a[x][2]<a[y][2];
    });
    solve(0,n-1);
    for(int i=0;i<n;i++) maxn[a[i]]=max(maxn[a[i]],sum[i]);
    for(int i=0;i<n;i++) sum[i]=maxn[a[i]]-(mp[a[i]]-1);

    int ans=0;
    for(int i=0;i<n;i++) ans+=(sum[i]==0);

    cout<<ans;

    return true&&false;
}

I. Mason’s Mark

tag

  • 模拟
  • 搜索

题意

给定 n⋅mn \cdot m 的方格，求其中有多少个 A,B,CA, B, C 。
其中 9≤n≤103,7≤m≤1039 \leq n \leq 10^3, 7 \leq m \leq 10^3 。

思路

垃圾题，直接搜即可，右边空的是 CC ，下面空的是 AA ，其余是 BB 。
复杂度 O(?)O(?) 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*
    Author: Cupids_Bow
    Time: 2022-09-29 12:37:33
*/
#include<bits/stdc++.h>
using namespace std;

using ll=long long;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n,m;
    cin>>m>>n;

    vector<string> s(n,"");
    for(int i=0;i<n;i++) cin>>s[i];

    int dx[]={-1,-1,-1,1,1,1,0,0},
        dy[]={-1,0,1,-1,0,1,-1,1};

    auto bfs=[&](int xs,int ys){
        queue<array<int,2>> q;
        q.push({xs,ys});
        s[xs][ys]='.';
        while(!q.empty()){
            auto [x,y]=q.front();
            q.pop();
            for(int i=0;i<8;i++){
                int xe=x+dx[i],
                    ye=y+dy[i];
                if(xe<0||xe>=n||ye<0||ye>=m||s[xe][ye]!='#') continue;
                s[xe][ye]='.';
                q.push({xe,ye});
            }
        }
    };

    auto check=[&](int xs,int ys){
        int X=0,Y=0;
        for(X=1;xs+X<n&&ys+X<m;X++) if(s[xs+X][ys+X]=='.') break;
        for(Y=1;ys+Y<m;Y++) if(s[xs][ys+Y]=='.') break;
        Y-=X*2;
        if(Y<=0) return 3;
        if(s[xs+X][ys+X+Y]=='.') return 2;
        else if(s[xs+X*2+Y*2][ys+X]=='.') return 0;
        else return 1;
    };

    array<int,3> ans={0,0,0};
    bfs(0,0);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++) if(s[i][j]=='#'){
            int flag=check(i,j);
            if(flag==3) continue;
            ans[flag]++;
            bfs(i,j);
        }
    
    cout<<ans[0]<<" "<<ans[1]<<" "<<ans[2];

    return true&&false;
}

K. Dishonest Driver

tag

  • kmp
  • 区间DP

题意

给定长为 nn 的字母串 ss ，求其化简后的最短长度。
化简规则为：

  • 连续一段相同的子串如 XXXXXX 可以化简为 X3X^3 化简后长度为 11

其中 1≤n≤7001 \leq n \leq 700 。

思路

区间 DPDP 。
dpl,rdp_{l,r} 表示 s[l,r]s[l, r] 化简后的最短长度，转移显然:

{dp[l][r]=min(dp[l][mid]+dp[mid+1][r])(l≤mid<r)dp[l][r]=min(dp[l][l+T−1]+dp[l+(r−l+1)/T∗T][r])(T为s[l,r]的最短循环节)dp[i][i]=1(1≤i≤n)dp[i][i−1]=0(2≤i≤n)\begin{cases} dp[l][r] = min(dp[l][mid] + dp[mid + 1][r]) (l \leq mid < r)\\ dp[l][r] = min(dp[l][l + T - 1] + dp[l+(r-l+1)/T*T][r]) (T 为 s[l, r] 的最短循环节)\\ dp[i][i] = 1 (1 \leq i \leq n)\\ dp[i][i - 1] = 0 (2 \leq i \leq n) \end{cases}

kmpkmp 处理循环节即可。
复杂度 O(n3)O(n^3) 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/*
    Author: Cupids_Bow
    Time: 2022-09-29 09:28:36
*/
#include<bits/stdc++.h>
using namespace std;

using ll=long long;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n;
    cin>>n;

    string s;
    cin>>s;
    
    vector<int> fail(n,0);
    vector<vector<int>> dp(n+1,vector<int>(n+1,0x3f3f3f3f));
    for(int i=0;i<=n;i++){
        dp[i][i]=1;
        if(i-1>=0) dp[i][i-1]=0;
    }
    for(int len=2;len<=n;len++){
        for(int l=0;l+len-1<n;l++){
            int r=l+len-1;
            for(int mid=l;mid<r;mid++) dp[l][r]=min(dp[l][r],dp[l][mid]+dp[mid+1][r]);
            fail[0]=-1;
            for(int i=1;i<r-l+1;i++){
                for(int j=fail[i-1];;j=fail[j]){
                    if(s[j+l+1]==s[i+l]){
                        fail[i]=j+1;
                        break;
                    }
                    else if(j==-1){
                        fail[i]=-1;
                        break;
                    }
                }
            }
            int T=r-l-fail[r-l];
            int L=l+(r-l+1)/T*T;
            dp[l][r]=min(dp[l][r],dp[l][l+T-1]+dp[L][r]);
        }
    }

    cout<<dp[0][n-1];

    return true&&false;
}