03 区域DP：三素数数

算法►动态规划►区域DP , , 评论

区域DP：三素数数

三素数数

题目背景

蛟川书院的一道练习题QAQ

题目描述

如果一个数的所有连续三位数字都是大于100的素数，则该数称为三素数数。比如113797是一个6位的三素数数。

输入格式

一个整数n（3 ≤ n ≤ 10000），表示三素数数的位数。

输出格式

一个整数，表示n位三素数的个数m，要求输出m除以10^9 + 9的余数。

样例 #1

样例输入 #1

1
4

样例输出 #1

1
204

提示

区域动归QAQ

设dp[k][i][j]表示到了第k位，这个数字是i，上一个数字是j的方案数

  • 初始化 dp[2][0→9][0→9]=1
  • 枚举第几位i，现在的数字now，之前的数字pre，上上个数字last
  • 如果last∗100+pre+10+now是素数，那么dp[i][now][pre]+=dp[i−1][pre][last]
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define int long long
using namespace std;
vector<int> prime;
int dp[10001][11][11]={0};
const int MOD=1e9+9;
vector<bool> is_prime(1001); // 0表示质数，1表示不是质数
void get_prime(int n)//欧拉筛板子
{
    is_prime[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (is_prime[i] == 0)
            prime.push_back(i);
        for (auto j : prime)
        {
            if (i * j > n)
                break;
            is_prime[i * j] = 1;
            if (i % j == 0)
                break;
        }
    }
    for(int i=0;i<=100;i++)is_prime[i]=1;
    //仅需要统计101~999的质数，剩下的不属于这个范围

}
int combine(int a,int b,int c)
{
    return a*100+b*10+c;
}
signed main()
{
    int n;
    cin>>n; get_prime(1000);
    for(int i=0;i<=9;i++)
        for(int j=0;j<=9;j++)
            dp[2][i][j]=1;
    for(int k=3;k<=n;k++)
    {
        for(int i=1;i<=9;i+=2)
        {
            for(int j=0;j<=9;j++)
            {
                for(int l=0;l<=9;l++)
                {
                    if(is_prime[combine(l,j,i)]==0)
                    dp[k][i][j]=(dp[k][i][j]+dp[k-1][j][l])%MOD;
                }

            }
        }
    }
    int ans=0;
    for(int i=0;i<=9;i++)for(int j=0;j<=9;j++)ans=(ans+dp[n][i][j])%MOD;
   cout<<ans<<endl;
    return 0;
}

另一道题目：Colo.

题目描述

小 F 和小 Y 经常在一起玩耍，因为小 F 是一个画家，他喜欢在一个长度为 n，宽度为 1 的网格图上画画，从左往右第 i 个方格被涂成了一种颜色 a_i。

你觉得他的随意涂鸦太难看了，想要保留恰好 k 种颜色（你不能保留没在网格图上出现的颜色），使得网格图上没被涂成任何一种你喜欢的颜色的网格都被剪掉，最后会剩下一些网格，你希望这些网格从左到右颜色的编号是单调不下降的。

此外，小 Y 使用的第 i 种颜色有一个价值 b_i，小 Y 看到了你裁剪后的网格图很是高兴，于是决定付给你你选择的颜色的价值总和。

你需要求出你能够获得的最大的价值是多少。

输入格式

第一行两个整数 n,k，表示小 Y 画画的网格图的大小和你需要保留颜色的种类数。
第二行 n 个整数 a_i，表示小 Y 画出来的网格图从左往右第 i 个格子的颜色。
第三行 n 个整数 b_i，表示第 i 种颜色的价值。

输出格式

一行一个整数，表示你能够获得的最大价值；特别地，如果无法找到选择颜色的方法满足要求，输出 -1。

样例 #1

样例输入 #1

1
2
3
5 2
1 2 1 3 2
5 3 1 100 100

样例输出 #1

1
6

样例 #2

样例输入 #2

1
2
3
10 3
1 3 4 2 9 3 4 2 5 1
1 5 2 3 9 8 1 2 3 10

样例输出 #2

1
-1

提示

【样例解释 #1】

对于第一组样例，我们可以选择 1 号和 3 号颜色保留，剩下的网格图即为 [1,1,3]，满足单调不下降这一个限制，获得的价值即为 b_1+b_3=5+1=6，可以证明这是最优的办法。

【数据范围】

对于所有测试数据，满足 1 \le n \le 500，1 \le k \le 500，1 \le a_i \le n，1 \le b_i \le 10^9。

各测试点的附加限制如下表所示。

本题开启捆绑测试，所有数据范围均相同的测试点捆绑为一个 \text{Subtask}。

测试点 n,k \le 特殊性质
1 \sim 3 10 无
4 \sim 5 100 无
6 \sim 10 500 不同的颜色不超过 10 种
11 \sim 15 500 每种颜色出现的次数不超过 2 次
16 \sim 20 500 无

首先是输入部分代码

在输入时候用bucket的方式记录每一种颜色的对应第一个和最后一个位置（后面有用）

记录方式用桶的方式便于查询

1
2
3
4
5
6
7
8
9
10
11
12
13
cin>>n>>k;
for(int i=1;i<=n;i++){
        cin>>a[i];
        if(bucket[a[i]].begin ==inf){
            bucket[a[i]].begin =i;
            bucket[a[i]].last =i;
        }
        else {
            bucket[a[i]].last =i;
        }
    }
for (int i=1;i<=n;i++)
        cin>>b[i];

接下来记录遍历每个颜色（对于每个颜色i） ，看看有哪些颜色（即j）在原数组中的位置是完全在他前面的，即 j 颜色的last小于 i 颜色的begin，(并且j<i由循环条件可知默认成立)。如果有的话加入到数组g的第 i 项指向的（可以这么理解）数组中去。表示在取 i 颜色时候，可以取 j 颜色作为他的前驱

1
2
3
4
5
6
7
8
9
10
11
12
13
14
long long g[505][505]={0}; 

for(int i=1;i<=n;i++){
        count=0;
        if(bucket[i].begin ==inf)continue;
        for(int j=1;j<i;j++){

            if(bucket[j].begin ==inf)continue;
            if(bucket[i].begin >bucket[j].last ){
                g[i][count]=j;
                count++;
            }
        }
    }

最重要的部分：填表

表格含义如下

1
2
3
4
5
6
7
8
9
for(int i=1;i<=n;i++)
        if(bucket[i].begin !=inf)
            dp[1][i]=b[i];
    for(int i=2;i<=k;i++)//i循环
        for(int j=i;j<=n;j++)//j循环
            if(bucket[j].begin !=inf && g[j][0]!=0)
                for(int p=0;g[j][p]!=0;p++)//p循环
                    if(dp[i-1][g[j][p]] !=0)
                        dp[i][j]=max(dp[i][j],dp[i-1][g[j][p]]+b[j]);//#

以样例二为例

关键数组信息

第一行循环设置递推初始调件；

第二个 i 循环，遍历从第二行到第k行，因为问的是选k个，再往下遍历没有意义

第三个 j 循环，遍历第 i 列到最后的值，ij用来定位每个位置

以上好像都是废话。。

第四个p循环，遍历当前所在位置的上一行中所有可能成为该位置前驱的位置，#处表示取这些通过状态转移方程到该位置的所有值的最大值

最后，遍历第k行找出所有可能情况的最大值，没有，则输出-1

1
2
3
4
5
6
long long maxf=0;
    for(int i=1;i<=n;i++)
        if(bucket[i].begin !=inf)
            maxf=max(maxf,dp[k][i]);
    if(maxf==0)maxf=-1;
    cout<<maxf<<endl;

完整代码附上

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
#include <bits/stdc++.h>
#define inf -1
using namespace std;

long long g[505][505]={0}; 
typedef struct{
    long long  begin;
    long long  last;
}edge;
edge bucket[505];
int main(void){
    long long n,k,a[505],b[505],dp[505][505]={0},count;
    cin>>n>>k;
    for(int i=0;i<=n;i++){
        bucket[i].begin =inf;
        bucket[i].last =inf;
    }

    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(bucket[a[i]].begin ==inf){
            bucket[a[i]].begin =i;
            bucket[a[i]].last =i;
        }
        else {
            bucket[a[i]].last =i;
        }
    }

    for (int i=1;i<=n;i++)
        cin>>b[i];


    for(int i=1;i<=n;i++){
        count=0;
        if(bucket[i].begin ==inf)continue;
        for(int j=1;j<i;j++){

            if(bucket[j].begin ==inf)continue;
            if(bucket[i].begin >bucket[j].last ){
                g[i][count]=j;
                count++;
            }
        }
    }
    for(int i=1;i<=n;i++)
        if(bucket[i].begin !=inf)
            dp[1][i]=b[i];
    for(int i=2;i<=k;i++)
        for(int j=i;j<=n;j++)
            if(bucket[j].begin !=inf && g[j][0]!=0)
                for(int p=0;g[j][p]!=0;p++)
                    if(dp[i-1][g[j][p]] !=0)
                        dp[i][j]=max(dp[i][j],dp[i-1][g[j][p]]+b[j]);

    long long maxf=0;
    for(int i=1;i<=n;i++)
        if(bucket[i].begin !=inf)
            maxf=max(maxf,dp[k][i]);
    if(maxf==0)maxf=-1;
    cout<<maxf<<endl;
    return 0;
}

XQC-1368我见青山多妩媚 料青山见我应如是

Harbin Institute of Technology, Shenzhen 计算机科学与技术 本科在读