[第三章]数学与简单dp

题目一解析

算法原理

代码实现

#include <iostream>
using namespace std;
int main()
{
    int p, q;
    cin >> p >> q;
    cout << (p - 1) * (q - 1) - 1 << endl;
    return 0;
}

题目二解析

算法原理

首先我们必须要明白两只蚂蚁相撞掉头可以看作时一只蚂蚁穿过了另一只蚂蚁，因为相撞之后两只蚂蚁都感冒了，掉不掉头其实无所谓，毕竟都感冒了，这样的话这题就简单多了。我们先不考虑特殊情况，先来看看一般情况：

第一只蚂蚁不管方向朝哪里，只要它右边的蚂蚁向左走就可能碰撞感染，同样，第一只蚂蚁左边的蚂蚁只要朝右边走也可能被感染，这样就很容易得到a n s = r i g h t + l e f t + 1 ans=right+left+1ans=right+left+1。这里l e f t leftleft表示左边蚂蚁向右走的数量，r i g h t rightright表示右边蚂蚁向左走的数量，1 11是指第一只蚂蚁本身。

还有一种特殊情况，就是当第一只蚂蚁向左走的时候，如果第一只蚂蚁左边没有向右爬行的蚂蚁，由于爬行速度相同，所以不管第一只蚂蚁右边有多少向左爬行的，其右边的蚂蚁永远不可能被感染。同理，当第一只蚂蚁向右走的时候，如果第一只蚂蚁右边没有向左爬行的蚂蚁，其左边也永远不可能感染。

代码实现

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n; 
int main()
{
  scanf("%d", &n);
  int pivot, left = 0, right = 0;
  scanf("%d", &pivot);
  for (int i = 1; i < n; i++)
  {
    int x;
    scanf("%d", &x);
    //找到感冒蚂蚁左边边且向右走的
    if (abs(x) < abs(pivot) && x > 0) right++;
    //找到感冒蚂蚁右边且向左走的
    if (abs(x) > abs(pivot) && x < 0) left++;
  }
  //特殊情况
  if ((pivot < 0 && right == 0) || pivot > 0 && left == 0) puts("1");
  else printf("%d\n", left + right + 1);
  
  return 0;
}

题目三解析

算法原理

算法一：模拟

代码实现

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int res = n;
    while (n >= 3)
    {
        res += n / 3; // res += [当前可兑换的瓶数]
        n = n / 3 + n % 3; //n = [当前可兑换的瓶数] + [兑换后剩余的瓶数]
    }
    cout << res << endl;
    return 0;
}

算法二：

当有3个空瓶时，可以兑换1瓶饮料，这时已经喝的饮料+1, 剩余空瓶为1

当有4个空瓶时，可以兑换1瓶饮料，这时已经喝的饮料+1, 剩余空瓶为2

当有5个空瓶时，可以兑换2瓶饮料，这是已经喝的饮料+2, 剩余空瓶为1

总空瓶里面，用1个瓶子来装兑换后的酒，每次兑换消耗2个空瓶。

每次兑换消耗3个空瓶，兑换1瓶饮料，又补充了1个空瓶，所以理解为每次兑换消耗2个空瓶、

（这个前提是空瓶的剩余数量 >= 3，也就是说如果空瓶数量为2时，不满足兑换条件。)

=> 总共n个空瓶, 拿出1个空瓶, 剩下的 n-1 个空瓶用来兑换, 每次兑换消耗2个空瓶。

代码实现

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    cout << n + (n - 1) / 2 << endl;
    return 0;
}

题目四解析

算法原理

1. 状态表示
   集合：定义f[i][j]为从(1, 1)到达(i, j)的所有方案
   属性：最大值
2. 状态转移
   (i, j)从(i-1, j)即上方过来
   (i, j)从(i, j-1)即左方过来
3. 空间压缩
   f[i][j]只需要用到这一层和上一层的f元素，所以可以压缩成滚动数组。在此之上，还可以直接压缩成一维数组。

代码实现

#include<iostream>
using namespace std;
const int N = 105;
int a[N][N], f[N][N];
int q, row, col;
int main()
{
    cin >> q;
    while(q--){
        cin >> row >> col;
        for(int i = 1; i <= row; i++){
            for(int j = 1; j <= col; j++){
                cin >> a[i][j];
            }
        }
        // f[i][j]指的是到(i, j)的最大花生数
        for(int i = 1; i <= row; i++){
            for(int j = 1; j <= col; j++){
                f[i][j] = max(f[i-1][j], f[i][j-1]) + a[i][j];
            }
        }
        cout << f[row][col] << endl;
    }
    return 0;
}

题目五解析

算法原理

最长上升子序列解题报告

给定一个长度为N的数列(w[N])，求数值严格单调递增的子序列的长度最长是多少。

样例

输入格式

第一行包含整数N。

第二行包含N个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

数据范围

1 ≤ N ≤ 1000，

−1e9 ≤ 数列中的数 ≤ 1e9

输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

算法1

(动态规划) O ( n 2 ) O(n^2)O(n2)

• 状态表示：f[i]表示从第一个数字开始算，以w[i]结尾的最大的上升序列。(以w[i]结尾的所有上升序列中属性为最大值的那一个)
  
• 状态计算（集合划分）：j∈(0,1,2,…,i-1), 在w[i] > w[j]时，
  f[i] = max(f[i], f[j] + 1)。
  有一个边界，若前面没有比i小的，f[i]为1（自己为结尾）。
  
• 最后在找f[i]的最大值。
  

时间复杂度

• O ( n 2 ) O(n^2)O(n2) 状态数(n nn) * 转移数(n nn)

代码实现

#include <iostream>
using namespace std;
const int N = 1010;
int n;
int w[N], f[N];
int main() 
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> w[i];
    
    int mx = 1;    // 找出所计算的f[i]之中的最大值，边算边找
    for (int i = 0; i < n; i++) 
    {
        f[i] = 1;    // 设f[i]默认为1，找不到前面数字小于自己的时候就为1
        for (int j = 0; j < i; j++) 
        {
            if (w[i] > w[j]) f[i] = max(f[i], f[j] + 1);    // 前一个小于自己的数结尾的最大上升子序列加上自己，即+1
        }
        mx = max(mx, f[i]);
    }
    
    cout << mx << endl;
    return 0;
}

算法2

(动态规划 + 二分) O ( n l o g n ) O(nlogn)O(nlogn)

• 状态表示：f[i]表示长度为i的最长上升子序列，末尾最小的数字。(长度为i的最长上升子序列所有结尾中，结尾最小min的) 即长度为i的子序列末尾最小元素是什么。
  
• 状态计算：对于每一个w[i], 如果大于f[cnt-1](*下标从0开始，*cnt长度的最长上升子序列，末尾最小的数字)，那就cnt+1，使得最长上升序列长度+1，当前末尾最小元素为w[i]。 若w[i]小于等于f[cnt-1],说明不会更新当前的长度，但之前末尾的最小元素要发生变化，找到第一个 大于或等于 (这里不能是大于) w[i]，更新以那时候末尾的最小元素。
  
• f[i]一定以一个单调递增的数组，所以可以用二分法来找第一个大于或等于w[i]的数字。
  

时间复杂度

• O ( n l o g n ) O(nlogn)O(nlogn) 状态数(n nn) * 转移数(l o g n lognlogn)

代码实现

#include <iostream>
using namespace std;
const int N = 1010;
int n, cnt;
int w[N], f[N];
int main() 
{
    cin >> n;
    for (int i = 0 ; i < n; i++) cin >> w[i];
    
    f[cnt++] = w[0];
    for (int i = 1; i < n; i++) 
    {
        if (w[i] > f[cnt-1]) f[cnt++] = w[i];
        else 
        {
            int l = 0, r = cnt - 1;
            while (l < r) 
            {
                int mid = (l + r) >> 1;
                if (f[mid] >= w[i]) r = mid;
                else l = mid + 1;
            }
            f[r] = w[i];
        }
    }
    cout << cnt << endl;
    return 0;
}

题目六解析

算法原理

设第一个数为 x xx，则第二个数为x + d 1 x+d_1x+d1，第三个数为x + d 1 + d 2 x+d_1+d_2x+d1+d2 …。这里的d 1 d_1d1，d 2 d_2d2表示a aa或者− b -b−b，所以这个数列为：

x xx, x + d 1 x + d_1x+d1, x + d 1 + d 2 x + d_1 + d_2x+d1+d2, x + d 1 + d 2 + d 3 x + d_1 + d_2 + d_3x+d1+d2+d3, …, x + d 1 + d 2 + . . . + d n − 1 x + d_1 + d_2 + ... + d_{n-1}x+d1+d2+...+dn−1，又因为数列之和为s，所以转化成：

n ∗ x + ( n − 1 ) ∗ d 1 + ( n − 2 ) ∗ d 2 + ( n − 3 ) ∗ d 3 + . . . + d n − 1 = s n * x + (n-1) * d_1 + (n-2) * d_2 + (n-3) * d_3 + ... + d_{n-1} = sn∗x+(n−1)∗d1+(n−2)∗d2+(n−3)∗d3+...+dn−1=s，再在一步转化：

s − [ ( n − 1 ) ∗ d 1 + ( n − 2 ) ∗ d 2 + ( n − 3 ) ∗ d 3 + . . . + d n − 1 ] n = x \frac{s - [(n-1) * d_1 + (n-2) * d_2 + (n-3) * d_3 + ...+ d_{n-1}]}{n} = xns−[(n−1)∗d1+(n−2)∗d2+(n−3)∗d3+...+dn−1]=x

因为x是任意整数，所以又转化成：

s ss与( n − 1 ) ∗ d 1 + ( n − 2 ) ∗ d 2 + ( n − 3 ) ∗ d 3 + . . . + d n − 1 (n-1) * d_1 + (n-2) * d_2 + (n-3) * d_3 + ...+ d_{n-1}(n−1)∗d1+(n−2)∗d2+(n−3)∗d3+...+dn−1 模n nn的余数相同。

到这里就转化成了组合问题。

下面就可以用dp分析法了。

1.状态表示：f[i][j]表示要选i个a或者-b且余数为j的所有集合的数量。

2.状态计算：第i个可以选a或者-b。

第i个选a：( n − 1 ) ∗ d 1 + ( n − 2 ) ∗ d 2 + ( n − 3 ) ∗ d 3 + . . . + 2 ∗ d n − 2 + a (n-1) * d_1 + (n-2) * d_2 + (n-3) * d_3 +...+ 2 * d_{n-2}+ a(n−1)∗d1+(n−2)∗d2+(n−3)∗d3+...+2∗dn−2+a 模 x = j x = jx=j。

则：( n − 1 ) ∗ d 1 + ( n − 2 ) ∗ d 2 + ( n − 3 ) ∗ d 3 + . . . + 2 ∗ d n − 2 (n-1) * d_1 + (n-2) * d_2 + (n-3) * d_3 +...+ 2 * d_{n-2}(n−1)∗d1+(n−2)∗d2+(n−3)∗d3+...+2∗dn−2 模 x = j − a x = j - ax=j−a。

系数和下标之和为n，所以第i项的的系数为n-i。

所以：f[i][j] = f[i - 1][j - (n - i) * a]

第i个选b：同理：f[i][j] = f[i - 1][j + (n - i) * b]

时间复杂度 O ( n 2 ) O(n^2)O(n2)

状态数量 * 状态转移时操作数 = (n - 1) * (n - 1) * 2

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010, MOD = 100000007;
int n, s, a, b;
int f[N][N];
int get_mod(int a, int b)
{
    return (a % b + b) % b;
}
int main()
{
    scanf("%d%d%d%d", &n, &s, &a, &b);
    
    f[0][0] = 1;
    for (int i = 1; i < n; i++)
        for (int j = 0; j < n; j++)
            f[i][j] = (f[i - 1][get_mod(j - (n - i) * a, n)] + f[i - 1][get_mod(j + (n  - i) * b, n)]) % MOD;
    
    printf("%d", f[n - 1][get_mod(s, n)]);
    return 0;
}