2022.02.17递推

1.划分数组

【题目描述】

给定一个长度为n的数列{ai}，要求划分最少的段数，使得每一段要么单调不降，要么单调不升。

【输入格式】

第一行一个整数n。

第二行n个整数表示数列{ai}。

【输出格式】

一行一个整数，表示最少的划分数。

【样例】

输入：

1 2 3 2 2 1

输出：

【思路】分别以last_max和last_min表示以i结尾的最长单调序列的起点的前一位，dp[i]表示a1~ai的最少划分段数

　　　　得递推式：dp[i]=min{dp[last_min(i)],dp[last_max(i)]}+1

【代码】

#include 
using namespace std;
int a[100001], last_min[100001], last_max[100001], dp[100001];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; ++i) {
        last_max[i] = i - 1;
        if (a[i] >= a[i - 1]) {
            last_max[i] = last_max[i - 1];//递推式
        }
        last_min[i] = i - 1;
        if (a[i] <= a[i - 1]) {
            last_min[i] = last_min[i - 1];//递推式
        }
        dp[i] = min(dp[last_min[i]], dp[last_max[i]]) + 1;//dp递推式
    }
    printf("%d", dp[n]);
    return 0;
}

2.求 f 函数

【题目描述】

给出一个函数：f(x)=f(f(x+11)) (x<=100)

　　　　　　　　　x-10(x>=101)

对于给定的x，求f(x)。

【输入格式】

输入包括若干行，每行一个正整数x，最后一行以0结束。

注意0不是要求的x，只是一个结束标记。

【输出格式】

对于每一个x，输出一行一个整数表示f(x)。

【样例】

输入：

100

101

输出：

【思路】

对于大于等于101的数容易求得答案，对于100以下的数因为出现了f(f(x+11))的结构则f(89)=f(100)，所以对于100以下的数结果可以通过递推求得。

又已知递推中最大值为100+11=111，求完101到111后从大到小求100以内即可

【代码】

#include
using namespace std;
int main() {
int f[112];
for (int i = 101; i <= 111; i++) {
f[i] = i - 10;
}
for (int i = 100; i >= 1; i--) {
f[i] = f[f[i + 11]];
}
int q;
while (scanf("%d", &q) && (q != 0)) {
if (q >= 101) {
printf("%d\n", q - 10);
} else {
printf("%d\n", f[q]);
}
}
return 0;
}

3.无限序列

【题目描述】

我们按以下方式产生序列：

1.初始时序列为1；

2.每一次变化都会将序列中的1变成10，0变成1。

经过无数次变化，我们得到序列1011010110110101101...

给出Q个询问，每次询问为：在区间[a,b]中有多少个1。

【输入格式】

第一行一个整数Q。

接下来Q行，每行两个整数a,b。

【输出格式】

对于每个询问，输出一行一个整数表示答案。

【样例】

输入：

2 8

输出：

【思路】

设经过i此变化得到序列为f(i)，f(i)=f(i-1)+f(i-2)，则第i个序列可以拆分成第i-1个序列和第i-2个序列。可以用递归处理。

注：序列变化的长度与其中包含1的数量分别为开头为1 2和1 1的斐波那契数列

【代码】

#include 
#define ll long long
using namespace std;
ll sizef[91], num1[91];
inline ll solve(ll v) {
    if (v == 0)
        return 0;
    int Max = 0;
    for (int i = 90; i >= 1; i--) {
        if (sizef[i] <= v) {
            Max = i;
            break;
        }
    }
    return num1[Max] + solve(v - sizef[Max]);
}
int main() {
    sizef[1] = 1;
    sizef[2] = 2;
    num1[1] = 1;
    num1[2] = 1;
    for (int i = 3; i <= 90; i++) {
        sizef[i] = sizef[i - 1] + sizef[i - 2];
        num1[i] = num1[i - 1] + num1[i - 2];
    }
    int q;
    scanf("%d", &q);
    ll a, b;
    for (int i = 1; i <= q; i++) {
        scanf("%lld%lld", &a, &b);
        printf("%lld\n", solve(b) - solve(a - 1));
    }
    return 0;
}

4.序列个数

【题目描述】

一个由1~n这n个数字组成的序列对于任意一个数i，要求满足b1,b2,...,bi中，小于等于i的数的个数恰好为ai的序列一共有多少个。

【输入格式】

第一行一个整数n。

接下来n个数，表示a1,a2,...,an。

【输出格式】

一行一个数，表示满足条件的排列数。

由于答案很大，只要求输出答案mod340610的结果。

【样例】

输入：

0 1 3

输出：

【思路】

可以将构造序列的过程转化为构造矩阵的过程，即在n*n的矩阵中放入n个1，要求每行每列只有一个1。

例：23415=0 1 0 0 0

　　　　　 0 0 1 0 0

　　　　　 0 0 0 1 0

　　　　　 1 0 0 0 0

　　　　　 0 0 0 0 1

所以ai可以看作以(1,1)为左上角、以(i,i)为右下角的矩阵中1的个数，a(i)-a(i-1)表示的是一个L形（左右颠倒）中1的个数。

然后就可以从(1,1)一层一层展开用乘法原理统计可能性

【代码】

#include 
using namespace std;
const int mod = 340610;
int main() {
    int n;
    long long ans = 1;
    scanf("%d", &n);
    int a[n + 1];
    a[0] = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] - a[i - 1] == 1) {
            ans *= (i * 2 - 1) - 2 * a[i - 1];
        }
        if (a[i] - a[i - 1] == 2) {
            ans *= ((i - 1) - a[i - 1]) * ((i - 1) - a[i - 1]);
        }
        if (a[i] - a[i - 1] >= 3) {
            ans = 0;
        }
        ans %= mod;
    }
    printf("%lld\n", ans);
    return 0;
}

5.平铺方案

【题目描述】

试问可以通过几种方式用2*1或2*2的瓦片平铺2*n的矩形。

【输入格式】

输入包括若干行。

每行一个整数n。

【输出格式】

对于每个n，输出一行一个整数，表示方案数。

【样例】

输入：

100

200

输出：

171

2731

845100400152152934331135470251

1071292029505993517027974728227441735014801995855195223534251

【思路】

设平铺2*i的矩形方案数为f(i)，在第i列竖着摆1*2方案数为f(i-1)，在第i与i-1列摆2*2方案数为f(i-2)，在第i与i-1列横摆2个2*1方案数为f(i-2)。

总递推式：f(i)=f(i-1)+f(i-2)+f(i-2)

注：小知识：简单加法比乘法运算速度快。

注：本题数据范围丧心病狂，需要用到高精度结构体。

【代码】

#include 
using namespace std;
struct BigInt {
    static const int M = 1000;
    int num[M + 10], len;
    BigInt() { clean(); }
    void clean() {
        memset(num, 0, sizeof(num));
        len = 1;
    }
    void write() {
        for (int i = len; i >= 1; i--) {
            printf("%d", num[i]);
        }
        printf("\n");
    }
    void itoBig(int x) {
        clean();
        while (x != 0) {
            num[len++] = x % 10;
            x /= 10;
        }
        if (len != 1)
            len--;
    }
    BigInt operator+(const BigInt &A) const {
        BigInt S;
        S.len = max(len, A.len);
        for (int i = 1; i <= S.len; i++) {
            S.num[i] += num[i] + A.num[i];
            if (S.num[i] >= 10) {
                S.num[i] -= 10;
                S.num[i + 1]++;
            }
        }
        while (S.num[S.len + 1]) S.len++;
        return S;
    }
} f[251];
int main() {
    f[0].itoBig(1), f[1].itoBig(1), f[2].itoBig(3);
    for (int i = 3; i <= 250; i++) {
        f[i] = f[i - 2] + f[i - 2] + f[i - 1];
    }
    int q;
    while (scanf("%d", &q) != (EOF)) {
        f[q].write();
    }
    return 0;
}

2022.02.17递推

相关

标签