TimusOJ-DP集锦

发表于 更新于 分类于

题目列表

1225. Flags

题意：有 nn 个格子排成一行，你需要将每个格子染成白、蓝、红三色之一，要求不能有两个相邻的同色格子，且蓝色必须在白色和红色之间。求方案数。

令 f[i][j]f[i][j] 表示前 ii 个格子，末尾状态为 jj 的方案数。有意义的状态共有四种：白、红、白蓝、红蓝。其中白可以由红蓝或红转移而来，红可以有白蓝或白转移而来，白蓝由白，红蓝由红。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
long long f[50][4];//0:white 1:red 2:white-blue 3:red-blue
signed main() {
    int n;
    cin>>n;
    f[1][0]=f[1][1]=1;
    for(int i=2;i<=n;i++) {
        f[i][0]=f[i-1][1]+f[i-1][3];
        f[i][1]=f[i-1][0]+f[i-1][2];
        f[i][2]=f[i-1][0],f[i][3]=f[i-1][1];
    }
    cout<<f[n][0]+f[n][1]<<endl;
    return 0;
}

1119. Metro

题意：有一个 n×mn\times m 的网格，你需要沿着网格线从 (0,0)(0,0) 走到 (n,m)(n,m)。单位长度为 100100。此外，有 kk 个格子允许从左下角直接走到右上角，距离为 1002100\sqrt{2}。问最短距离。

令 f[i][j]f[i][j] 表示从 (0,0)(0,0) 走到 (i,j)(i,j) 的最短距离，则可以由 f[i−1][j]+100f[i-1][j]+100 和 f[i][j−1]+100f[i][j-1]+100 转移而来。如果允许穿对角线，则也可以由 f[i−1][j−1]+1002f[i-1][j-1]+100\sqrt{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
#include<bits/stdc++.h>
using namespace std;
bool a[1010][1010];
double f[1010][1010];
signed main() {
    double sq2=100*sqrt(2);
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++) {
        int x,y;
        cin>>x>>y;
        a[x][y]=1;
    }
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++) {
            if(i==0&&j==0) continue;
            f[i][j]=1e9;
            if(a[i][j]) f[i][j]=min(f[i][j],f[i-1][j-1]+sq2);
            if(i!=0) f[i][j]=min(f[i][j],f[i-1][j]+100);
            if(j!=0) f[i][j]=min(f[i][j],f[i][j-1]+100);
        }
    cout<<int(f[n][m]+0.5)<<endl;
    return 0;
}

1146. Maximum Sum

题意：一个 n×mn\times m 的矩阵，每个格子有一个整数（可以为负数），求最大子矩阵和。

预处理二维前缀和，n4n^4 暴力枚举子矩阵。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
int a[110][110],s[110][110];
signed main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            s[i][j]=s[i][j-1]+a[i][j];
    for(int j=1;j<=n;j++)
        for(int i=1;i<=n;i++)
            s[i][j]+=s[i-1][j];
    int ans=-1e9;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=i;k++)
                for(int l=1;l<=j;l++)
                    ans=max(ans,s[i][j]-s[i][l-1]-s[k-1][j]+s[k-1][l-1]);
    cout<<ans<<endl;
    return 0;
}

1203. Scientific Conference

题意：有 nn 个区间 [l,r][l,r]，问最多能选出多少不重叠的区间。

按 rr 从小到大排序，贪心选择。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
struct node{int l,r;} a[100010];
signed main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].l>>a[i].r;
    sort(a+1,a+n+1,[](node x,node y) {
        if(x.r==y.r) return x.l>y.l;
        return x.r<y.r;
    });
    int now=0,ans=0;
    for(int i=1;i<=n;i++) {
        if(a[i].l<=now) continue;
        ans++,now=a[i].r;
    }
    cout<<ans<<endl;
    return 0;
}

1009. K-based Numbers

题意：求有多少个 nn 位的 KK 进制数（不含前导零），满足在 KK 进制下没有两个相邻的 00。

f[i][j]f[i][j] 表示考虑前 nn 位，最后一位是 jj 的方案数，则若 j≠0,f[i][j]=∑0≤k<Kf[i−1][k]j\ne 0,f[i][j]=\sum\limits_{0\le k<K} f[i-1][k]，否则 f[i][j]=∑0<k<Kf[i−1][k]f[i][j]=\sum\limits_{0<k<K} f[i-1][k]。用前缀和维护即可达到 O(nk)O(nk)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
long long f[20][11],s[20][11];
signed main() {
    int n,k;
    cin>>n>>k;
    for(int i=1;i<k;i++)
        f[1][i]=1,s[1][i]=i;
    for(int i=2;i<=n;i++)
        for(int j=0;j<k;j++) {
            if(j==0) f[i][j]=s[i-1][k-1]-s[i-1][0],s[i][j]=f[i][j];
            else f[i][j]=s[i-1][k-1],s[i][j]=s[i][j-1]+f[i][j];
        }
    cout<<s[n][k-1]<<endl;
    return 0;
}

2018. The Debut Album

题意：求有多少个 nn 位的 01 串，满足不存在超过 aa 个连续的 0、不存在超过 bb 个连续的 1。

设 f[i][j∈{0,1}][k]f[i][j\in\{0,1\}][k] 表示前 ii 位，最后一位为 jj 且持续 kk 个的方案数，则 f[i][j][k]=f[i−1][j][k−1]+∑f[i−1][!j][x]f[i][j][k]=f[i-1][j][k-1]+\sum f[i-1][!j][x]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int f[2][2][310],s[2][2];
signed main() {
    int n,a[2];
    cin>>n>>a[0]>>a[1];
    f[1][0][1]=f[1][1][1]=1,s[1][0]=s[1][1]=1;
    for(int i=2;i<=n;i++) {
        int t=(i&1);
        s[t][0]=s[t][1]=0;
        for(int x=0;x<=1;x++)
            for(int j=1;j<=a[x];j++) {
                f[t][x][j]=f[t^1][x][j-1];
                if(j==1) (f[t][x][j]+=s[t^1][x^1])%=mod;
                (s[t][x]+=f[t][x][j])%=mod;
            }
    }
    cout<<(s[n&1][0]+s[n&1][1])%mod<<endl;
    return 0;
}

1353. Milliard Vasya’s Function

题意：求 10910^9 以内有多少个数的各数位之和为 ss。

f[i][j]f[i][j] 表示 ii 位数中有多少个数的各数位之和为 jj，则 f[i][j]=∑0≤k≤9f[i−1][j−k]f[i][j]=\sum\limits_{0\le k\le 9} f[i-1][j-k]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
long long f[10][90];
signed main() {
    int s,ans=0;
    cin>>s;
    for(int i=1;i<=9;i++)
        f[1][i]=1;
    for(int i=2;i<=9;i++)
        for(int j=0;j<=81;j++)
            for(int k=max(0,j-9);k<=j;k++)
                f[i][j]+=f[i-1][k];
    for(int i=1;i<=9;i++)
        ans+=f[i][s];
    if(s==1) ans++;
    cout<<ans<<endl;
    return 0;
}

1260. Nudnik Photographer

题意：求有多少个 1∼n1\sim n 的排列 pp，满足 p1=1,∣pi−pi−1∣≤2p_1=1,|p_i-p_{i-1}|\le 2。

考虑从左到右填排列。第一位填了 11，假设接下来填了 3,53,5，则会发现剩下的填法已经完全确定了。总结可以发现，一定是填满前面某些位，然后跳到头再跳回来。问题转化为填满前面某些位的方案数。设 f[i][0/1]f[i][0/1] 表示填满前 ii 位，最后一位填 i/i−1i/i-1 的方案数，则 f[i][0]=f[i−1][0]+f[i−1][1],f[i][1]=f[i−2][0]f[i][0]=f[i-1][0]+f[i-1][1],f[i][1]=f[i-2][0]。思考得最终答案为 f[1][0]+f[2][0]+⋯+f[n−1][0]+f[n−1][1]f[1][0]+f[2][0]+\cdots+f[n-1][0]+f[n-1][1]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
long long f[60][2];
signed main() {
    int n;
    cin>>n;
    if(n==1) {
        cout<<1<<endl;
        return 0;
    }
    f[1][0]=1;
    for(int i=2;i<=n;i++)
        f[i][0]=f[i-1][0]+f[i-1][1],f[i][1]=f[i-2][0];
    long long ans=0;
    for(int i=1;i<n;i++)
        ans+=f[i][0];
    cout<<ans+f[n-1][1]<<endl;
    return 0;
}

1167. Bicolored Horses

题意：有一个长度为 nn 的 01 串，你需要将它划分成 kk 个部分，每个部分不能为空。每部分的代价为该部分 0 的个数乘 1 的个数，求最小总代价。

令 f[i][j]f[i][j] 表示前 ii 位划分 jj 个部分的最小代价，则可以由 f[k][j−1]f[k][j-1] 转移而来，0 和 1 的个数用前缀和处理即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
int s[2][510],f[510][510];
signed main() {
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) {
        int x;
        cin>>x;
        s[x][i]=s[x][i-1]+1;
        s[x^1][i]=s[x^1][i-1];
    }
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=min(i,k);j++)
            for(int l=0;l<i;l++)
                f[i][j]=min(f[i][j],f[l][j-1]+(s[0][i]-s[0][l])*(s[1][i]-s[1][l]));
    cout<<f[n][k]<<endl;
    return 0;
}

1073. Square Country

题意：给你一个数 nn，求最少能用多少个完全平方数的和表示出来（可以重复使用）。

设 f[i]f[i] 表示 ii 最少能用多少个完全平方数表示出来，则 f[i]=min⁡j2≤if[i−j2]+1f[i]=\min\limits_{j^2\le i} f[i-j^2]+1。复杂度 O(nn)O(n\sqrt{n})。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
int f[60010];
signed main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) {
        f[i]=1e9;
        for(int j=1;j*j<=i;j++)
            f[i]=min(f[i],f[i-j*j]+1);
    }
    cout<<f[n]<<endl;
    return 0;
}

1586. Threeprime Numbers

题意：求有多少个 nn 位十进制数，满足任意相邻的三位均为质数。

考虑预处理出所有三位质数，并对每个两位数处理出以它为前两位的所有满足条件的第三位。令 f[i][j]f[i][j] 表示有多少个满足条件的 ii 位数且最后两位为 jj，则使用刷表法可以更新 f[i+1][k]f[i+1][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
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+9;
bool isprime(int n) {
    int stop=n/6+1,Tstop=sqrt(n)+5;
    if(n==2||n==3||n==5||n==7||n==11)
        return 1;
    if(n%2==0||n%3==0||n%5==0||n==1)
        return 0;
    for(int i=1;i<=stop;i++) {
        if(i*6>=Tstop) break;
        if(n%(i*6+1)==0||n%(i*6+5)==0)
            return 0;
    }
    return 1;
}
vector<int> a[100];
int f[10010][110];
signed main() {
    int n;
    cin>>n;
    for(int i=100;i<=999;i++)
        if(isprime(i)) {
            a[i/10].push_back(i%10);
            f[3][i%100]++;
        }
    for(int i=4;i<=n;i++)
        for(int j=0;j<100;j++)
            for(int v:a[j])
                (f[i][j%10*10+v]+=f[i-1][j])%=mod;
    int ans=0;
    for(int i=0;i<100;i++)
        (ans+=f[n][i])%=mod;
    cout<<ans<<endl;
    return 0;
}

1017. Staircases

题意：求有多少个序列 aa 满足 len>1len>1 且 ∀i<len,ai<ai+1,∑ai=n\forall i<len, a_i<a_i+1,\sum a_i=n。

设 f[i][j]f[i][j] 表示有多少个和为 ii，最后一位为 jj 的序列。则 f[i][j]=∑k<jf[i−j][k]f[i][j]=\sum\limits_{k<j}f[i-j][k]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
long long f[510][510];
signed main() {
    int n;
    cin>>n;
    f[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=i;j>0;j--)
            for(int k=0;k<j;k++)
                f[i][j]+=f[i-j][k];
    long long ans=0;
    for(int i=1;i<n;i++)
        ans+=f[n][i];
    cout<<ans<<endl;
    return 0;
}

1152. False Mirrors

题意：有一个长度为 nn 的环，第 ii 位上有 aia_i 只怪物，每次攻击可以选择相邻的三个位置并杀掉上面的所有怪物。每次操作后受到存活怪物个数的伤害。问杀掉所有怪物的最小总伤害。

考虑 DFS，传入三个参数：nownow 表示当前还剩多少个位置有怪物；sumsum 表示当前剩的怪物个数；nowfnowf 表示当前受到的伤害。维护一个 visvis 数组表示当前已经杀掉了哪些位置的怪物（转移、回溯维护）。转移时暴力枚举杀怪的位置，检查这三个位置中哪些有怪，计算新受到的伤害。当没有位置剩余的时候返回。一个重要的剪枝时维护当前搜到的最优解，如果受到的伤害已经超过了最优解则直接返回。

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
#include<bits/stdc++.h>
using namespace std;
int n,a[22],vis[22],minn=1e9;
int pre(int x) {return x==1?n:x-1;}
int nxt(int x) {return x==n?1:x+1;}
void dfs(int now,int sum,int nowf) {
    if(now==0) {
        minn=min(nowf,minn);
        return;
    }
    if(nowf>=minn) return;
    for(int i=1;i<=n;i++) {
        if(vis[i]) continue;
        int tmp=0,f1=0,f2=0,pr=pre(i),nx=nxt(i);
        vis[i]=1,tmp+=a[i];
        if(!vis[pr]) {
            vis[pr]=1;
            tmp+=a[pr];
            f1=1;
        }
        if(!vis[nx]) {
            vis[nx]=1;
            tmp+=a[nx];
            f2=1;
        }
        int t=sum-tmp;
        dfs(now-1-f1-f2,t,nowf+t);
        vis[i]=0,vis[pr]=!f1,vis[nx]=!f2;
    }
}
int main() {
    scanf("%d",&n);
    int sum=0;
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    memset(vis,0,sizeof(vis));
    dfs(n,sum,0);
    printf("%d\n",minn);
    return 0;
}

2072. Kirill the Gardener 3

题意：有 nn 个格子排成一行，第 ii 个格子有一个颜色 aia_i。你需要按颜色单调不降的顺序访问这些格子，访问和移动一格的时间均为 11，求最小时间花费。

可以发现，对于每个颜色要么从左到右扫、要么从右到左扫。我们可以预处理出每个颜色的左端点和右端点，于是可以设 f[i][0/1]f[i][0/1] 表示考虑前 ii 个颜色，以左端点/右端点结尾的最小用时，则 DP 转移是显然的。

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[100010],b[100010],cnt=0;
int l[100010],r[100010];
int f[100010][2];
signed main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        b[++cnt]=a[i];
    }
    sort(b+1,b+cnt+1);
    cnt=unique(b+1,b+cnt+1)-b-1;
    for(int i=1;i<=n;i++) {
        a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
        if(l[a[i]]==0) l[a[i]]=i;
        r[a[i]]=i;
    }
    l[0]=r[0]=1;
    for(int i=1;i<=cnt;i++) {
        f[i][0]=min(f[i-1][0]+abs(l[i-1]-r[i]),f[i-1][1]+abs(r[i-1]-r[i]))+r[i]-l[i];
        f[i][1]=min(f[i-1][0]+abs(l[i-1]-l[i]),f[i-1][1]+abs(r[i-1]-l[i]))+r[i]-l[i];
    }
    cout<<min(f[cnt][0],f[cnt][1])+n<<endl;
    return 0;
}

1013. K-based Numbers. Version 3

题意：求有多少个 nn 位 kk 进制数（无前导零），满足没有两个相邻的 00。结果对 mm 取模。（2≤n,m,k≤10182\le n,m,k\le 10^{18}）

考虑普通的 DP：我们从低位往高位考虑，设 f[i]f[i] 表示 ii 位的满足条件个数。最后一位（最高位）只有 k−1k-1 种可能，倒数第二位可以是 00 也可以不是 00。如果是 00 相当于跳过了一位，为 f[i−2]f[i-2]；如果不是 00 则为 f[i−1]f[i-1]。故 f[i]=(k−1)(f[i−1]+f[i−2])f[i]=(k-1)(f[i-1]+f[i-2])。这个 DP 方程可以使用矩阵加速计算，设状态矩阵为 [f[i]f[i−1]]\begin{bmatrix}f[i]\\f[i-1]\end{bmatrix}，则转移为：

[f[i]f[i−1]]=[k−1k−110][f[i−1]f[i−2]]\begin{bmatrix}f[i]\\f[i-1]\end{bmatrix}=\begin{bmatrix}k-1&k-1\\1&0\end{bmatrix}\begin{bmatrix}f[i-1]\\f[i-2]\end{bmatrix}

注意到此题模数达到了 101810^{18} 级别，乘法会爆 long long，需要使用快速乘。

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
int mod;
int mul(int a,int b,int res=0) {
    for(;b;a=(a+a)%mod,b>>=1)
        if(b&1) res=(res+a)%mod;
    return res;
}
struct matrix {
    int n,m;
    int a[4][4];
    matrix operator*(const matrix &o)const {
        matrix res;
        res.n=n,res.m=o.m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=o.m;j++) {
                res.a[i][j]=0;
                for(int k=1;k<=m;k++)
                    (res.a[i][j]+=mul(a[i][k],o.a[k][j]))%=mod;
            }
        return res;
    }
};
matrix ksm(matrix a,int b) {
    matrix res=a;b--;
    for(;b;b>>=1,a=a*a)
        if(b&1) res=res*a;
    return res;
}
signed main() {
    int n,k;
    cin>>n>>k>>mod;
    if(n==2) {
        cout<<mul((k-1),k)<<endl;
        return 0;
    }
    matrix ans,trans;
    ans.n=2,ans.m=1;
    ans.a[1][1]=mul((k-1),k),ans.a[2][1]=(k-1)%mod;
    trans.n=trans.m=2;
    trans.a[1][1]=trans.a[1][2]=(k-1)%mod;
    trans.a[2][1]=1,trans.a[2][2]=0;
    ans=ksm(trans,n-2)*ans;
    cout<<ans.a[1][1]<<endl;
    return 0;
}

1635. Mnemonics and Palindromes

题意：给你一个字符串 ss，将它分为尽可能少的回文子串。

我们可以 n2n^2 预处理出来所有的回文子串，然后设 f[i]f[i] 表示前 ii 位最少能分多少个回文子串，则 f[i]=min⁡s[j+1,i] is palindromef[j]+1f[i]=\min\limits_{s[j+1,i]\text{ is palindrome}} f[j]+1。方案使用 prepre 数组统计一下即可。

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
#include<bits/stdc++.h>
using namespace std;
bool ishui[4010][4010],vis[4010];
int f[4010],pre[4010];
signed main() {
    string s;
    cin>>s;
    s=" "+s;
    for(int i=1;i<s.size();i++)
        for(int j=0;j<i&&i+j<s.size();j++)
            if(s[i-j]==s[i+j]) ishui[i-j][i+j]=1;
            else break;
    for(int i=1;i<s.size();i++)
        for(int j=0;j<i-1&&i+j<s.size();j++)
            if(s[i-j-1]==s[i+j]) ishui[i-j-1][i+j]=1;
            else break;
    f[0]=0,pre[0]=-1;
    for(int i=1;i<s.size();i++) {
        f[i]=1e9;
        for(int j=0;j<i;j++)
            if(ishui[j+1][i]&&f[j]+1<f[i])
                f[i]=f[j]+1,pre[i]=j;
    }
    cout<<f[s.size()-1]<<endl;
    int now=pre[s.size()-1];
    for(;now>=0;now=pre[now])
        vis[now]=1;
    for(int i=1;i<s.size();i++) {
        cout<<s[i];
        if(vis[i]) cout<<" ";
    }
    cout<<endl;
    return 0;
}

1183. Brackets Sequence

题意：给你一个包含小括号和中括号的括号序列，问如何添加插入尽可能少的括号使得该序列合法。

注意到一个性质：如果一个括号需要插入字符使其匹配，则一定插入在它旁边直接匹配。于是可以考虑区间 DP：f[i][j]f[i][j] 表示从 ii 到 jj 的子串至少需要添加多少个字符才能合法，则：f[i][j]=min⁡i≤k<jf[i][k]+f[k+1][j]f[i][j]=\min\limits_{i\le k<j} f[i][k]+f[k+1][j]。特殊地，如果 s[i]s[i] 和 s[j]s[j] 本身可以匹配，还可以由 f[i+1][j−1]f[i+1][j-1] 转移而来。

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
#include<bits/stdc++.h>
using namespace std;
string s;
int n,f[110][110],pre[110][110];
bool check(char x,char y) {
    if(x=='('&&y==')') return 1;
    if(x=='['&&y==']') return 1;
    return 0;
}
void dfs(int l,int r) {
    if(l>r) return;
    if(l==r) {
        if(s[l]=='('||s[l]==')') cout<<"()";
        else cout<<"[]";
    }
    else if(pre[l][r]==-1) {
        cout<<s[l];
        dfs(l+1,r-1);
        cout<<s[r];
    }
    else dfs(l,pre[l][r]),dfs(pre[l][r]+1,r);
}
signed main() {
    cin>>s;
    n=s.size(),s=" "+s;
    for(int i=1;i<=n;i++) f[i][i]=1;
    for(int len=2;len<=n;len++)
        for(int i=1;i<=n;i++) {
            int j=i+len-1;
            if(j>n) break;
            f[i][j]=1e9;
            if(check(s[i],s[j])) f[i][j]=f[i+1][j-1],pre[i][j]=-1;
            for(int k=i;k<j;k++)
                if(f[i][k]+f[k+1][j]<f[i][j]) {
                    f[i][j]=f[i][k]+f[k+1][j];
                    pre[i][j]=k;
                }
        }
    dfs(1,n);
    cout<<endl;
    return 0;
}

1658. Sum of Digits

题意：求最小的十进制数使得各位之和为 s1s_1，各位的平方之和位 s2s_2。如果解的位数大于 100100 则判为无解。多组数据。

由于有多组数据，考虑预处理出所有情况。由于解的位数在 100100 以内，所以 s1≤900,s2≤8100s_1\le 900,s_2\le 8100，所以可以设 f[i][j]f[i][j] 表示和为 ii，平方和为 jj 的最小位数，则 f[i][j]=min⁡k≤i&k2≤jf[i−k][j−k2]+1f[i][j]=\min\limits_{k\le i\& k^2\le j}f[i-k][j-k^2]+1。使用 prepre 数组记录答案。在解的位数确定的情况下，要求字典序最小即为答案最小，所以 DP 的时候优先从较小的 kk 转移即可保证最优。

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
#include<bits/stdc++.h>
using namespace std;
int f[910][8110],pre[910][8110];
void init() {
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(int i=1;i<=900;i++)
        for(int j=1;j<=8100;j++)
            for(int k=1;k<=9;k++)
                if(k<=i&&k*k<=j&&f[i-k][j-k*k]+1<f[i][j])
                    f[i][j]=f[i-k][j-k*k]+1,pre[i][j]=k;
}
vector<int> ans;
void get(int n,int m) {
    if(n==0) return;
    get(n-pre[n][m],m-pre[n][m]*pre[n][m]);
    ans.push_back(pre[n][m]);
}
signed main() {
    init();
    int t;
    cin>>t;
    while(t--) {
        ans.clear();
        int n,m;
        cin>>n>>m;
        if(n>m||n>900||m>8100) cout<<"No solution"<<endl;
        else if(f[n][m]>100) cout<<"No solution"<<endl;
        else {
            get(n,m);
            sort(ans.begin(),ans.end());
            for(int v:ans) cout<<v;
            cout<<endl;
        }
    }
    return 0;
}

1244. Gentlemen

题意：给你一个可重集，问是否存在唯一的和为 mm 的子集，如果存在输出方案。

令 f[i][j]f[i][j] 表示集合的前 ii 个元素组成和为 jj 的方案数，则 f[i][j]=f[i−1][j]+f[i−1][j−a[i]]f[i][j]=f[i-1][j]+f[i-1][j-a[i]]，第一维可以省略。

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
#include<bits/stdc++.h>
using namespace std;
int a[110],f[100010],pre[100010];
bool vis[110];
signed main() {
    int n,m;
    cin>>m>>n;
    f[0]=1;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        for(int j=m;j>=a[i];j--) {
            if(f[j]==0) pre[j]=i;
            f[j]+=f[j-a[i]];
        }
    }
    if(f[m]==0) cout<<0<<endl;
    else if(f[m]>1) cout<<-1<<endl;
    else {
        int now=m;
        while(now!=0)
            vis[pre[now]]=1,now-=a[pre[now]];
        for(int i=1;i<=n;i++)
            if(!vis[i]) cout<<i<<" ";
        cout<<endl;
    }
    return 0;
}

1081. Binary Lexicographic Sequence

题意：求长度为 nn 的、没有两个相邻的 1 的 01 串中的字典序第 kk 小。

设 f[i][0/1]f[i][0/1] 表示 ii 位，最高位为 0/10/1 的方案数。于是可以递归的计算第 kk 小：若当前位选 00 的方案数就大于等于 kk，则一定选 00，否则选 11，然后 kk 减去 00 的方案数。

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
#include<bits/stdc++.h>
using namespace std;
int f[50][2];
signed main() {
    int n,k;
    cin>>n>>k;
    f[1][0]=f[1][1]=1;
    for(int i=2;i<=n;i++)
        f[i][0]=f[i-1][0]+f[i-1][1],f[i][1]=f[i-1][0];
    int now=-1;
    for(int i=1;i<=n;i++)
        if(f[i][0]+f[i][1]>=k) {
            now=i;
            break;
        }
    if(now==-1) cout<<-1<<endl;
    else {
        for(int i=n;i>now;i--) cout<<0;
        while(now>0) {
            if(f[now][0]>=k) {
                cout<<0;
                now--;
            }
            else {
                cout<<1;
                k-=f[now][0],now--;
            }
        }
        cout<<endl;
    }
    return 0;
}

1501. Sense of Beauty

题意：有两个 01 串 a,ba,b，每次可以从任意一个串的开头删除一个元素，要求在任意时刻删除的 0 和删除的 1 个数相差不超过 11。输出方案或无解。

考虑每次选两个，则必须选一个 0 一个 1。令 f[i][j]f[i][j] 表示能否选完 aa 的前 ii 位和 bb 的前 jj 位，则可能由 f[i−1][j−1],f[i−2][j],f[i][j−2]f[i-1][j-1],f[i-2][j],f[i][j-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
#include<bits/stdc++.h>
using namespace std;
bool f[1010][1010];
short pre[1010][1010];
void get(int x,int y) {
    if(x==0&&y==0) return;
    if(pre[x][y]==1) {
        get(x-1,y-1);
        cout<<"12";
    }
    else if(pre[x][y]==2) {
        get(x-2,y);
        cout<<"11";
    }
    else {
        get(x,y-2);
        cout<<"22";
    }
}
signed main() {
    int n;
    string s,t;
    cin>>n>>s>>t;
    f[0][0]=1;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++) {
            if(i==0&&j==0) continue;
            if(i&&j&&s[i-1]!=t[j-1]&&f[i-1][j-1])
                f[i][j]=1,pre[i][j]=1;
            if(i>1&&s[i-1]!=s[i-2]&&f[i-2][j])
                f[i][j]=1,pre[i][j]=2;
            if(j>1&&t[j-1]!=t[j-2]&&f[i][j-2])
                f[i][j]=1,pre[i][j]=3;
        }
    if(!f[n][n]) cout<<"Impossible"<<endl;
    else get(n,n),puts("");
    return 0;
}

1018. Binary Apple Tree

题意：一棵有根的二叉树，边有边权，你需要保留若干条边（删掉其他边），使得剩下的边仍然与根连通，求剩下的边权和最大值。

设 f[i][j]f[i][j] 表示以 ii 为根的子树，保留 jj 条边的最大边权和，则可以由 f[lson][k]+f[rson][j−2−k]f[lson][k]+f[rson][j-2-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
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int> > a[110];
int n,m,sum,f[110][110];
void dfs(int now,int fa) {
    pair<int,int> tmp[3];
    int cnt=0;
    for(auto [v,w]:a[now])
        if(v!=fa)
            dfs(v,now),tmp[++cnt]={v,w};
    if(cnt==0) return;
    auto [v1,w1]=tmp[1];
    auto [v2,w2]=tmp[2];
    for(int i=1;i<=m;i++) {
        f[now][i]=max(f[v1][i-1]+w1,f[v2][i-1]+w2);
        for(int j=0;j<i-1;j++)
            f[now][i]=max(f[now][i],f[v1][j]+f[v2][i-2-j]+w1+w2);
    }
}
signed main() {
    cin>>n>>m;
    for(int i=1;i<n;i++) {
        int u,v,w;
        cin>>u>>v>>w;
        a[u].push_back({v,w});
        a[v].push_back({u,w});
    }
    dfs(1,0);
    cout<<f[1][m]<<endl;
    return 0;
}

1117. Hierarchy

题意：有一棵 231−12^{31}-1 个点的、严格平衡的二叉搜索树。每次在两个点之间移动的花费为中间点的个数（不包括这两个点）。求 l→l+1→l+2→⋯→rl\to l+1\to l+2\to\cdots\to r 的花费。

首先思路上可以使用差分简化计算：1→r1\to r 的花费减去 1→l1\to l 的花费。注意到，每次在两个点 a,ba,b 之间移动的花费为 ∣log⁡(lowbit(r))−log⁡(lowbit(l))∣|\log(lowbit(r))-\log(lowbit(l))|。这个式子是启发我们可以用 22 的幂来递推。我们可以预处理出 1→2n1\to 2^n 的答案，则从 1→x1\to x 的答案可以用类似快速幂的思路来二进制分解计算。

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
int d[35];
signed main() {
    d[1]=d[2]=0;
    for(int i=3;i<=31;i++)
        d[i]=d[i-1]*2+2*(i-2);
    for(int i=1;i<=31;i++)
        d[i]+=(i-1);
    int l,r;
    cin>>l>>r;
    auto solve=[&](int x) {
        int ans=0;
        for(int i=31;i>=0;i--)
            if(x>=(1ll<<i)) {
                x-=1ll<<i;
                ans+=d[i];
                if(x>0)ans+=i-1;
            }
        return ans;
    };
    cout<<abs(solve(r)-solve(l))<<endl;
    return 0;
}

1741. Communication Fiend

题意：有一个系统，当前处在版本 11，且为正版系统。有 mm 个升级包，第 ii 个升级包从版本 uiu_i 升级到版本 viv_i（ui<viu_i<v_i），花费为 wiw_i。升级包分为三种：正版、盗版、半正版。其中正版升级包只能对正版系统升级，盗版和半正版可以对任何系统升级。盗版升级包会将系统变为盗版系统，且在此后的操作中系统永远都是盗版。求从 11 升到 nn 的最小代价。

设 f[i][0/1]f[i][0/1] 表示升级到第 ii 版且状态为正版/盗版的最小花费。转移显然。

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
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,pair<int,string> > > a[10010];
long long f[10010][2];
void chkmin(long long &x,long long y) {x=min(x,y);}
signed main() {
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        int u,v,w;
        string op;
        cin>>u>>v>>w>>op;
        a[u].push_back({v,{w,op}});
    }
    memset(f,0x3f,sizeof(f));
    f[1][0]=0;
    for(int i=1;i<n;i++) {
        for(auto tmp:a[i]) {
            auto [v,tt]=tmp;
            auto [w,op]=tt;
            if(op=="Pirated")
                chkmin(f[v][1],min(f[i][0],f[i][1])+w);
            else if(op=="Cracked") {
                chkmin(f[v][0],f[i][0]+w);
                chkmin(f[v][1],f[i][1]+w);
            }
            else chkmin(f[v][0],f[i][0]+w);
        }
    }
    if(f[n][0]>=1e18&&f[n][1]>=1e18)
        cout<<"Offline"<<endl;
    else cout<<"Online"<<endl<<min(f[n][0],f[n][1])<<endl;
    return 0;
}

1346. Intervals of Monotonicity

题意：给你一个序列 aa，问最少能分成多少个单调不升/单调不降的子段。

设 f[i][0/1]f[i][0/1] 表示前 ii 位，当前上升/下降的最少子段数，则可以由 f[i−1][0],f[i−1][1]f[i-1][0],f[i-1][1] 转移而来：可以开启新的数列，也（可能）可以接着上一个序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
int a[100010],f[100010][2];
void chkmin(int &x,int y) {x=min(x,y);}
signed main() {
    int tmpa,tmpb;
    cin>>tmpa>>tmpb;
    int n=tmpb-tmpa+1;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    memset(f,0x3f,sizeof(f));
    f[1][0]=f[1][1]=1;
    for(int i=2;i<=n;i++) {
        if(a[i]<=a[i-1]) chkmin(f[i][0],f[i-1][0]);
        if(a[i]>=a[i-1]) chkmin(f[i][1],f[i-1][1]);
        chkmin(f[i][0],f[i-1][0]+1);
        chkmin(f[i][0],f[i-1][1]+1);
        chkmin(f[i][1],f[i-1][0]+1);
        chkmin(f[i][1],f[i-1][1]+1);
    }
    cout<<min(f[n][0],f[n][1])<<endl;
    return 0;
}

1223. Chernobyl’ Eagle on a Roof

题意：有 nn 个鹰蛋和 mm 层楼，每个鹰蛋有一个相同的硬度 EE，使得它在第 EE 层楼往下摔摔不坏，而在第 E+1E+1 层楼往下摔会摔坏。你需要通过这 nn 个鹰蛋测试出它们的硬度，每次可以选一层楼扔一个鹰蛋，如果碎了就不能再用，如果没碎就可以继续使用。求最坏情况下的最小测试次数。n,m≤1000n,m\le 1000。多组数据。

首先有一个显然的 nm2nm^2 DP，设 f[i][j]f[i][j] 表示有 ii 个鹰蛋，已经确定答案在某 jj 个楼层中选择了，要最终确定硬度所需的最小操作次数。

如果只有一个鹰蛋，显然 f[1][j]=jf[1][j]=j，因为只有一次摔碎的机会，只能一层一层试。接下来，转移方程为 f[i][j]=min⁡1≤k≤j{max⁡(f[i−1][k−1],f[i][j−k])}+1f[i][j]=\min\limits_{1\le k\le j}\{\max(f[i-1][k-1],f[i][j-k])\}+1：假设我们在第 kk 层扔了一次鹰蛋，如果碎了，答案一定更低，可以确定在 [1,k−1][1,k-1] 之间；如果没碎，答案可能更高，可以确定在 [k,j][k,j] 之间。由于我们不知道会不会碎，所以要考虑到最坏情况，即为这两种次数的最大值；但我们可以决定选择哪个 kk 扔最优，所以对每个 kk 取 min⁡\min 得到答案。

这时的复杂度为 O(nm2)O(nm^2)，显然不能通过本题，于是我们考虑优化。

  1. 注意到，如果我们有超过 log⁡(m+1)\log(m+1) 个鹰蛋可供使用，一定可以直接二分查找，此时的测试次数达到理论下界，为 log⁡(m+1)\log(m+1)（m+1m+1 是因为有可能所有楼层都摔不坏，额外多出一种情况）。所以我们只需要考虑 n<log⁡(m+1)n<\log(m+1) 的情况即可。于是我们将一个 O(n)O(n) 优化成了 O(log⁡m)O(\log m)，总复杂度 O(m2log⁡m)O(m^2\log m)。
  2. 在 ii 相同的情况下，显然 jj 越大需要的次数越多，所以 f[i]f[i] 单调递增（非严格）。观察转移方程，发现我们的每一种决策为两项的较大值，而那两项一个单调递增、一个单调递减，所以 max⁡\max 的图像会形成一个向下凸的单峰函数，二分即可找到 min⁡\min 的位置。于是我们又将一个 O(m)O(m) 优化成了 O(log⁡m)O(\log m)，复杂度变为 O(mlog⁡2m)O(m\log^2 m)。

优化 3：由于此优化过于复杂，单独开一个板块。此优化将状态转移进一步优化成 O(1)O(1)，总而将复杂度变为 O(mlog⁡m)O(m\log m)。

  • 我们可以发现一个性质：f[i]f[i] 不仅单调递增，而且每次增加的量不超过 11。因为鹰蛋个数相同时，如果增加一层楼，最坏也可以直接在一楼试一次，转化为原楼层数的情况。于是我们每次只需要判断 f[i][j]f[i][j] 是否可以与 f[i][j−1]f[i][j-1] 相等即可。
  • 转移方程为若干项取 min⁡\min，所以真正的答案必然比每一项都要小（或相等），即 ∀k,ans≤max⁡(f[i−1][k−1],f[i][j−k])+1\forall k,ans\le\max(f[i-1][k-1],f[i][j-k])+1。我们换一种表示方法，令 p=j−kp=j-k，则 k=j−pk=j-p，于是有 ∀p,ans≤max⁡(f[i−1][j−p−1],f[i][p])+1\forall p,ans\le\max(f[i-1][j-p-1],f[i][p])+1。
  • 我们考虑什么时候 f[i][j]=f[i][j−1]f[i][j]=f[i][j-1]：如果这一项的 max⁡\max 值取的是后者，则要求 f[i][p]+1=f[i][j−1]f[i][p]+1=f[i][j-1]，此时 f[i][p]=f[i][j−1]−1f[i][p]=f[i][j-1]-1。我们维护最后一个满足此条件的 pp，因为前者是单调递减的，在后者相同的情况下，pp 越大越有可能满足条件。此时，我们只需比较 f[i][p]f[i][p] 是否大于等于 f[i−1][j−p−1]f[i-1][j-p-1]，只要大于等于，那么 f[i][j]f[i][j] 必然可以取到 f[i][j−1]f[i][j-1]。
  • 上面我们说明了，只要 f[i][p]≥f[i−1][j−p−1]f[i][p]\ge f[i-1][j-p-1] 时，答案一定能取到 f[i][j−1]f[i][j-1]，那么如果不满足呢？此时一定取不到。当 f[i][p]f[i][p] 小于 f[i−1][j−p−1]f[i-1][j-p-1] 时，如果答案的位置 pp 满足 f[i][p]=f[i][j−1]f[i][p]=f[i][j-1]，+1+1 后显然不能取到 f[i][j−1]f[i][j-1] 的值；如果答案的位置 pp 满足 f[i][p]<f[i][j−1]−1f[i][p]<f[i][j-1]-1，由于在 f[i][p]=f[i][j−1]−1f[i][p]=f[i][j-1]-1 时以已经小于了 f[i−1][j−p−1]f[i-1][j-p-1]，而 f[i][p]f[i][p] 向左单调递减，f[i−1][j−p−1]f[i-1][j-p-1] 向左单调递增，所以在左边一定还是 f[i−1][j−p−1]f[i-1][j-p-1] 取到最大值，一定取不到 f[i][j−1]f[i][j-1]。此时，我们最好也只能取到 f[i][j−1]+1f[i][j-1]+1，而前面已经说明 f[i][j−1]+1f[i][j-1]+1 是一定可以取到的。综上，我们便将状态转移优化成了 O(1)O(1)。

优化 1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
int f[17][1010],lg[1010];
signed main() {
    lg[1]=0;
    for(int i=2;i<=1001;i++)
        lg[i]=lg[(i+1)/2]+1;
    for(int i=0;i<=1000;i++)
        f[1][i]=i;
    for(int i=2;i<=15;i++)
        for(int j=1;j<=1000;j++) {
            f[i][j]=1e9;
            for(int k=1;k<=j;k++)
                f[i][j]=min(f[i][j],max(f[i-1][k-1],f[i][j-k])+1);
        }
    int n,m;
    while(cin>>n>>m&&(n||m)) {
        if(n>=lg[m+1]) cout<<lg[m+1]<<endl;
        else cout<<f[n][m]<<endl;
    }
    return 0;
}

优化 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
#include<bits/stdc++.h>
using namespace std;
int f[17][1010],lg[1010],pre[17][1010];
signed main() {
    lg[1]=0;
    for(int i=2;i<=1001;i++)
        lg[i]=lg[(i+1)/2]+1;
    for(int i=0;i<=1000;i++)
        f[1][i]=i;
    for(int i=2;i<=15;i++)
        for(int j=1;j<=1000;j++) {
            int l=1,r=j;
            while(l+1<r) {
                int mid=(l+r)/2;
                if(f[i-1][mid-1]==f[i][j-mid])
                    l=r=mid;
                else if(f[i-1][mid-1]<f[i][j-mid])
                    l=mid;
                else r=mid;
            }
            f[i][j]=max(f[i-1][l-1],f[i][j-l])+1;
            f[i][j]=min(f[i][j],max(f[i-1][r-1],f[i][j-r])+1);
        }
    int n,m;
    while(cin>>n>>m&&(n||m)) {
        if(n>=lg[m+1]) cout<<lg[m+1]<<endl;
        else cout<<f[n][m]<<endl;
    }
    return 0;
}

优化 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
#include<bits/stdc++.h>
using namespace std;
int f[17][1010],lg[1010],pre[17][1010];
signed main() {
    lg[1]=0;
    for(int i=2;i<=1001;i++)
        lg[i]=lg[(i+1)/2]+1;
    for(int i=0;i<=1000;i++)
        f[1][i]=i;
    for(int i=2;i<=15;i++) {
        int p=0;
        f[i][1]=1;
        for(int j=2;j<=1000;j++) {
            if(f[i][p]>=f[i-1][j-p-1])
                f[i][j]=f[i][j-1];
            else f[i][j]=f[i][j-1]+1,p=j-1;
        }
    }
    int n,m;
    while(cin>>n>>m&&(n||m)) {
        if(n>=lg[m+1]) cout<<lg[m+1]<<endl;
        else cout<<f[n][m]<<endl;
    }
    return 0;
}

当然，空间上也可以使用滚动数组优化成 O(m)O(m)。

1036. Lucky Tickets

题意：问有多少个长度为 2n2n 的十进制数字串（允许前导零），满足前后两部分的各位数之和相等，且总的各位数之和为 ss。

首先，如果 ss 为奇数显然无解，所以只考虑 ss 为偶数，此时前后两部分的和均为 s/2=s′s/2=s'。由于两部分完全独立，所以只需要考虑一部分的方案数，平方即可。设 f[i][j]f[i][j] 表示 ii 位，和为 jj 的方案数，则 f[i][j]=∑0≤k≤min⁡(9,j)f[i−1][j−k]f[i][j]=\sum\limits_{0\le k\le\min(9,j)}f[i-1][j-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
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
#include<bits/stdc++.h>
using namespace std;
const int MAXL=100;
struct Int {
    int len,z[MAXL];
    Int() {memset(z,0,sizeof(z));len=1;}
    void clean_pre_zero() {while(len>1&&!z[len-1])len--;}
    void read() {char s[MAXL];scanf("%s",s);*this=s;}
    void print() {for(int i=len-1;i>=0;i--)printf("%d",z[i]);}
    Int operator=(const char *num) {
        len=strlen(num);
        for(int i=0;i<len;i++)
            z[i]=num[len-i-1]-'0';
        return *this;
    }
    Int operator=(const int &num) {
        char s[MAXL];
        sprintf(s,"%d",num);
        return *this=s;
    }
    Int(const int num) {*this=num;}
    Int(const char *num) {*this=num;}
    Int operator+(const Int &b) {
        Int res;
        res.len=max(len,b.len)+1;
        for(int i=0;i<res.len;i++)
            res.z[i]=z[i]+b.z[i];
        for(int i=0;i<res.len;i++)
            res.z[i+1]+=res.z[i]/10,res.z[i]%=10;
        res.clean_pre_zero();
        return res;
    }
    Int operator-(const Int &b) {
        Int res;
        res.len=len;
        for(int i=0;i<res.len;i++)
            res.z[i]=z[i]-b.z[i];
        for(int i=0;i<res.len;i++)
            if(res.z[i]<0) {
                res.z[i+1]+=res.z[i]/10-1;
                res.z[i]%=10,res.z[i]+=10;
            }
        res.clean_pre_zero();
        return res;
    }
    Int operator*(const Int &b) {
        Int res;
        res.len=len+b.len;
        for(int i=0;i<len;i++)
            for(int j=0;j<b.len;j++)
                res.z[i+j]+=z[i]*b.z[j];
        for(int i=0;i<res.len;i++)
            res.z[i+1]+=res.z[i]/10,
            res.z[i]%=10;
        res.clean_pre_zero();
        return res;
    }
    Int operator/(const Int &b) {
        Int res,cur;
        res.len=len;
        for(int i=len-1;i>=0;i--) {
            cur=cur*10+z[i];
            while(cur>=b)
                cur=cur-b,res.z[i]++;
        }
        res.clean_pre_zero();
        return res;
    }
    Int operator%(const Int &b) {
        Int res,cur;
        res.len=len;
        for(int i=len-1;i>=0;i--) {
            cur=cur*10+z[i];
            while(cur>=b)
                cur=cur-b,res.z[i]++;
        }
        cur.clean_pre_zero();
        return cur;
    }
    bool operator<(const Int &b)const {
        if(len!=b.len) return len<b.len;
        for(int i=len-1;i>=0;i--)
            if(z[i]!=b.z[i])
                return z[i]<b.z[i];
        return false;
    }
    bool operator>(const Int &b)const {return b<*this;}
    bool operator==(const Int &b)const {return !(*this>b)&&!(*this<b);}
    bool operator>=(const Int &b)const {return *this>b||*this==b;}
    bool operator<=(const Int &b)const {return *this<b||*this==b;}
    bool operator!=(const Int &b)const {return !(b==*this);}
    void operator+=(const Int &b) {*this=*this+b;}
    void operator-=(const Int &b) {*this=*this-b;}
    void operator*=(const Int &b) {*this=*this*b;}
    void operator/=(const Int &b) {*this=*this/b;}
    void operator%=(const Int &b) {*this=*this%b;}
};
Int f[55][1010];
signed main() {
    int n,s;
    cin>>n>>s;
    if(s%2!=0) {
        cout<<0<<endl;
        return 0;
    }
    s/=2;
    f[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=s;j++)
            for(int k=0;k<=min(9,j);k++)
                f[i][j]+=f[i-1][j-k];
    (f[n][s]*f[n][s]).print();
    puts("");
    return 0;
}

1029. Ministry

题意：有一个 nn 行 mm 列的矩阵，你需要从第 11 行的任意一个点走到第 nn 行的任意一个点，要求经过的格子权值和尽可能小，输出方案。

设 f[i][j]f[i][j] 表示走到 (i,j)(i,j) 的最小代价，则首先将它从 f[i−1][j]f[i-1][j] 转移过来，然后考虑同层之间的转移，从左到右、从右到左分别扫一遍处理即可。

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[110][510],s[110][510];
int f[110][510],pre[110][510];
//0:down 1:left 2:right
void get(int x,int y) {
    if(x==0) return;
    if(pre[x][y]==0) get(x-1,y);
    else if(pre[x][y]==1) get(x,y-1);
    else get(x,y+1);
    cout<<y<<" ";
}
signed main() {
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) {
            cin>>a[i][j];
            s[i][j]=s[i][j-1]+a[i][j];
        }
    for(int i=1;i<=m;i++)
        f[1][i]=a[1][i];
    for(int i=2;i<=n;i++) {
        for(int j=1;j<=m;j++)
            f[i][j]=f[i-1][j]+a[i][j];
        for(int j=2;j<=m;j++)
            if(f[i][j-1]+a[i][j]<f[i][j]) {
                f[i][j]=f[i][j-1]+a[i][j];
                pre[i][j]=1;
            }
        for(int j=m-1;j>0;j--)
            if(f[i][j+1]+a[i][j]<f[i][j]) {
                f[i][j]=f[i][j+1]+a[i][j];
                pre[i][j]=2;
            }
    }
    int mini=1;
    for(int i=2;i<=m;i++)
        if(f[n][i]<f[n][mini]) mini=i;
    get(n,mini);
    cout<<endl;
    return 0;
}

1078. Segments

题意：数轴上有 nn 个线段，你需要从中选出一个尽可能长的线段序列，使得序列中每个线段都严格被下一个线段包含（端点不能重合）。

注意到长度短的线段一定不可能包含长度长的，所以我们可以按长度从小到大排序，于是转化为简单的 n2n^2 DP 了：f[i]f[i] 表示以 ii 结尾的最长线段序列长度，则 f[i]=max⁡segj⊂segi{f[j]+1}f[i]=\max\limits_{seg_j\subset seg_i}\{f[j]+1\}。

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
#include<bits/stdc++.h>
using namespace std;
struct seg {
    int l,r,num;
} a[510];
int f[510],pre[510];
void get(int x) {
    if(x==0) return;
    get(pre[x]);
    cout<<a[x].num<<" ";
}
signed main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i].l>>a[i].r;
        a[i].num=i;
    }
    sort(a+1,a+n+1,[](seg a,seg b) {
        return a.r-a.l<b.r-b.l;
    });
    for(int i=1;i<=n;i++) {
        f[i]=1,pre[i]=0;
        for(int j=1;j<=i;j++)
            if(a[i].l<a[j].l&&a[i].r>a[j].r)
                if(f[j]+1>f[i])
                    f[i]=f[j]+1,pre[i]=j;
    }
    int maxi=1;
    for(int i=2;i<=n;i++)
        if(f[i]>f[maxi]) maxi=i;
    cout<<f[maxi]<<endl;
    get(maxi);
    cout<<endl;
    return 0;
}