头像

incra

$$\href{https://www.acwing.com/blog/content/22674/}{\Huge\color{blue}{个人主页}}$$$$\Large{封禁家族六年级蒟蒻}$$




离线:12小时前


最近来访(890)
用户头像
SYYHSYAL
用户头像
Fatin
用户头像
Zhang_ch14
用户头像
sinten
用户头像
懒狗出世
用户头像
井底之蛙
用户头像
算法之王
用户头像
星星星星丶星
用户头像
迎风飘扬
用户头像
大好河山
用户头像
mp4
用户头像
夏旭日
用户头像
TheSea
用户头像
猿生猿长
用户头像
Principal_Shang
用户头像
cry_sky
用户头像
文成公主
用户头像
markding
用户头像
GabrielxD
用户头像
种花家的蒟蒻


incra
12小时前

<—点个赞吧QwQ

宣传一下算法提高课整理

在网友的国度中共有 $n$ 种不同面额的货币,第 $i$ 种货币的面额为 $a[i]$,你可以假设每一种货币都有无穷多张。

为了方便,我们把货币种数为 $n$、面额数组为 $a[1..n]$ 的货币系统记作 $(n,a)$。 

在一个完善的货币系统中,每一个非负整数的金额 $x$ 都应该可以被表示出,即对每一个非负整数 $x$,都存在 $n$ 个非负整数 $t[i]$ 满足 $a[i] × t[i]$ 的和为 $x$。

然而,在网友的国度中,货币系统可能是不完善的,即可能存在金额 $x$ 不能被该货币系统表示出。

例如在货币系统 $n=3, a=[2,5,9]$ 中,金额 $1,3$ 就无法被表示出来。 

两个货币系统 $(n,a)$ 和 $(m,b)$ 是等价的,当且仅当对于任意非负整数 $x$,它要么均可以被两个货币系统表出,要么不能被其中任何一个表出。 

现在网友们打算简化一下货币系统。

他们希望找到一个货币系统 $(m,b)$,满足 $(m,b)$ 与原来的货币系统 $(n,a)$ 等价,且 $m$ 尽可能的小。

他们希望你来协助完成这个艰巨的任务:找到最小的 $m$。

输入格式

输入文件的第一行包含一个整数 $T$,表示数据的组数。

接下来按照如下格式分别给出 $T$ 组数据。 

每组数据的第一行包含一个正整数 $n$。

接下来一行包含 $n$ 个由空格隔开的正整数 $a[i]$。

输出格式

输出文件共有 $T$ 行,对于每组数据,输出一行一个正整数,表示所有与 $(n,a)$ 等价的货币系统 $(m,b)$ 中,最小的 $m$。

数据范围

$1 \le n \le 100$,
$1 \le a[i] \le 25000$,
$1 \le T \le 20$

输入样例:

2 
4 
3 19 10 6 
5 
11 29 13 19 17

输出样例:

2
5

思路

这道题和货币系统(一)是同一个代码,就输出要改一下。
这里的数如果在新的系统中有的话,必然不能被其他数凑出来,而如果不能被其他书凑出来,就说明这个数只能被它自己表示出来。即把所有$f_i==1$的数个数统计一下即可。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110,M = 25010;
int n,m;
int a[N];
int f[M];
int main () {
    int T;
    cin >> T;
    while (T--) {
        memset (f,0,sizeof (f));
        cin >> n;
        m = 0;
        for (int i = 1;i <= n;i++) {
            cin >> a[i];
            m = max (m,a[i]);
        }
        sort (a + 1,a + 1 + n);
        f[0] = 1;
        for (int i = 1;i <= n;i++) {
            for (int j = a[i];j <= m;j++) f[j] += f[j - a[i]];
        }
        int ans = 0;
        for (int i = 1;i <= n;i++) ans += (f[a[i]] == 1);
        cout << ans << endl;
    }
    return 0;
}



incra
13小时前

<—点个赞吧QwQ

宣传一下算法提高课整理

给你一个n种面值的货币系统,求组成面值为m的货币有多少种方案。

输入格式

第一行,包含两个整数n和m。

接下来n行,每行包含一个整数,表示一种货币的面值。

输出格式

共一行,包含一个整数,表示方案数。

数据范围

$n \le 15, m \le 3000$

输入样例:

3 10
1
2
5

输出样例:

10

思路

这题和买书是同一个思路。

代码

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 3010;
int n,m;
LL f[N];
int main () {
    cin >> n >> m;
    f[0] = 1;
    for (int i = 1;i <= n;i++) {
        int x;
        cin >> x;
        for (int j = x;j <= m;j++) f[j] += f[j - x];
    }
    cout << f[m] << endl;
    return 0;
}


新鲜事 原文

incra
13小时前
阅读量2w祭



incra
15小时前

<—点个赞吧QwQ

宣传一下算法提高课整理

小明手里有n元钱全部用来买书,书的价格为10元,20元,50元,100元。

问小明有多少种买书方案?(每种书可购买多本)

输入格式

一个整数 n,代表总共钱数。

输出格式

一个整数,代表选择方案种数。

数据范围

$0 \le n \le 1000$

输入样例1:

20

输出样例1:

2

输入样例2:

15

输出样例2:

0

输入样例3:

0

输出样例3:

1

思路

可以转化为完全背包问题求方案数:

  • 将总和 $n$ 看作背包容量
  • 将每个数 $a_i$ 看作体积为 $a_i$ 的物品

代码

#include <iostream>
using namespace std;
const int N = 1010;
int n;
int a[] = {0,10,20,50,100},f[N];
int main () {
    cin >> n;
    f[0] = 1;
    for (int i = 1;i <= 4;i++) {
        for (int j = a[i];j <= n;j++) f[j] += f[j - a[i]];
    }
    cout << f[n] << endl;
    return 0;
}



incra
15小时前

小凯手中有两种面值的金币,两种面值均为正整数且彼此互素。

每种金币小凯都有无数个。

在不找零的情况下,仅凭这两种金币,有些物品他是无法准确支付的。

现在小凯想知道在无法准确支付的物品中,最贵的价值是多少金币?

注意:输入数据保证存在小凯无法准确支付的商品。

输入格式

输入数据仅一行,包含两个正整数 $a$ 和 $b$,它们之间用一个空格隔开,表示小凯手中金币的面值。

输出格式

输出文件仅一行,一个正整数 $N$,表示不找零的情况下,小凯用手中的金币不能准确支付的最贵的物品的价值。

数据范围

$1 \le a,b \le 10^9$

输入样例:

3 7

输出样例:

11

思路

代码

#include <iostream>
using namespace std;
typedef long long LL;
LL a,b;
int main () {
    cin >> a >> b;
    cout << a * b - a - b << endl;
}



incra
1天前

<—点个赞吧QwQ

宣传一下算法提高课整理

给定 $N$ 个正整数 $A_1,A_2,…,A_N$,从中选出若干个数,使它们的和为 $M$,求有多少种选择方案。

输入格式

第一行包含两个整数 $N$ 和 $M$。

第二行包含 $N$ 个整数,表示 $A_1,A_2,…,A_N$。

输出格式

包含一个整数,表示可选方案数。

数据范围

$1 \le N \le 100$,
$1 \le M \le 10000$,
$1 \le A_i \le 1000$,
答案保证在 int 范围内。

输入样例:

4 4
1 1 2 2

输出样例:

3

思路

可以转化为$0/1$背包问题求方案数:

  • 将总和 $m$ 看作背包容量
  • 将每个数 $a_i$ 看作体积为 $A_i$ 的物品

代码

#include <iostream>
using namespace std;
const int N = 10010;
int n,m;
int f[N];
int main () {
    cin >> n >> m;
    f[0] = 1;
    for (int i = 1;i <= n;i++) {
        int x;
        cin >> x;
        for (int j = m;j >= x;j--) f[j] += f[j - x];
    }
    cout << f[m] << endl;
    return 0;
}



incra
1天前

<—点个赞吧QwQ

宣传一下算法提高课整理

宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。

一天,小智和皮卡丘来到了小精灵狩猎场,里面有很多珍贵的野生宠物小精灵。

小智也想收服其中的一些小精灵。

然而,野生的小精灵并不那么容易被收服。

对于每一个野生小精灵而言,小智可能需要使用很多个精灵球才能收服它,而在收服过程中,野生小精灵也会对皮卡丘造成一定的伤害(从而减少皮卡丘的体力)。

当皮卡丘的体力小于等于0时,小智就必须结束狩猎(因为他需要给皮卡丘疗伤),而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。

当小智的精灵球用完时,狩猎也宣告结束。

我们假设小智遇到野生小精灵时有两个选择:收服它,或者离开它。

如果小智选择了收服,那么一定会扔出能够收服该小精灵的精灵球,而皮卡丘也一定会受到相应的伤害;如果选择离开它,那么小智不会损失精灵球,皮卡丘也不会损失体力。

小智的目标有两个:主要目标是收服尽可能多的野生小精灵;如果可以收服的小精灵数量一样,小智希望皮卡丘受到的伤害越小(剩余体力越大),因为他们还要继续冒险。

现在已知小智的精灵球数量和皮卡丘的初始体力,已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。

请问,小智该如何选择收服哪些小精灵以达到他的目标呢?

输入格式

输入数据的第一行包含三个整数:N,M,K,分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。

之后的K行,每一行代表一个野生小精灵,包括两个整数:收服该小精灵需要的精灵球的数量,以及收服过程中对皮卡丘造成的伤害。

输出格式

输出为一行,包含两个整数:C,R,分别表示最多收服C个小精灵,以及收服C个小精灵时皮卡丘的剩余体力值最多为R。

数据范围

$0 < N \le 1000$,
$0 < M \le 500$,
$0 < K \le 100$

输入样例1:

10 100 5
7 10
2 40
2 50
1 20
4 20

输出样例1:

3 30

输入样例2:

10 100 5
8 110
12 10
20 10
5 200
1 110

输出样例2:

0 100

思路

这题就是二位费用的背包,只需要注意一些细节问题。

代码

#include <iostream>
using namespace std;
const int N1 = 1010,N2 = 510;
int n,m1,m2;
int f[N1][N2];
int main () {
    cin >> m1 >> m2 >> n;
    for (int i = 1;i <= n;i++) {
        int w1,w2;
        cin >> w1 >> w2;
        for (int j1 = m1;j1 >= w1;j1--) {
            for (int j2 = m2 - 1;j2 >= w2;j2--) f[j1][j2] = max (f[j1][j2],f[j1 - w1][j2 - w2] + 1);    //皮卡丘的血量等于0是不合法的
        }
    }
    int cost_health = m2;
    for (int i = 0;i <= m2 - 1;i++) {   //皮卡丘的血量等于0是不合法的
        if (f[m1][i] == f[m1][m2 - 1]) cost_health = min (cost_health,i);   //选最小的
    }
    cout << f[m1][m2 - 1] << ' ' << m2 - cost_health << endl;
    return 0;
}



incra
1天前

<—点个赞吧QwQ

宣传一下算法提高课整理

有一个箱子容量为 V,同时有 n 个物品,每个物品有一个体积(正整数)。

要求 n 个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。

输入格式

第一行是一个整数 V,表示箱子容量。

第二行是一个整数 n,表示物品数。

接下来 n 行,每行一个正整数(不超过10000),分别表示这 n 个物品的各自体积。

输出格式

一个整数,表示箱子剩余空间。

数据范围

$0 < V \le 20000$,
$0 < n \le 30$

输入样例:

24
6
8
3
12
7
9
7

输出样例:

0

思路

这道题是$0/1$背包,我们把体积作为价值,这样求出来的$f_i$就是体积为$i$的最大装入空间

代码

#include <iostream>
using namespace std;
const int N = 20010;
int n,m;
int f[N];
int main () {
    cin >> m >> n;
    for (int i = 1;i <= n;i++) {
        int x;
        cin >> x;
        for (int j = m;j >= x;j--) f[j] = max (f[j],f[j - x] + x);
    }
    cout << m - f[m] << endl;
    return 0;
}



incra
1天前

<—点个赞吧QwQ

宣传一下算法提高课整理

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。

但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。

某天,雷达捕捉到敌国的导弹来袭。

由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数,导弹数不超过1000),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

共一行,输入导弹依次飞来的高度。

输出格式

第一行包含一个整数,表示最多能拦截的导弹数。

第二行包含一个整数,表示要拦截所有导弹最少要配备的系统数。

数据范围

雷达给出的高度数据是不大于 $30000$ 的正整数,导弹数不超过 $1000$。

输入样例:

389 207 155 300 299 170 158 65

输出样例:

6
2

思路

第一问就是最长不上升子序列的长度,直接用最长上升子序列的思路就好了。
第二问具体见这里

代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n = 0;
int a[N],f[N];
int main () {
    while (cin >> a[n + 1]) n++;
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        f[i] = 1;
        for (int j = 1;j < i;j++) {
            if (a[j] >= a[i]) f[i] = max (f[i],f[j]+1);
        }
        ans = max (ans,f[i]);
    }
    cout << ans << endl;
    ans = 0;
    for (int i = 1;i <= n;i++) {
        f[i] = 1;
        for (int j = 1;j < i;j++) {
            if (a[j] < a[i]) f[i] = max (f[i],f[j]+1);
        }
        ans = max (ans,f[i]);
    }
    cout << ans << endl;
    return 0;
}



incra
1天前

<—点个赞吧QwQ

宣传一下算法提高课整理

给定一个长度为 $N$ 的数组,数组中的第 $i$ 个数字表示一个给定股票在第 $i$ 天的价格。

设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

  • 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
  • 卖出股票后,你无法在第二天买入股票 (即冷冻期为 $1$ 天)。

输入格式

第一行包含整数 $N$,表示数组长度。

第二行包含 $N$ 个不超过 $10000$ 的正整数,表示完整的数组。

输出格式

输出一个整数,表示最大利润。

数据范围

$1 \le N \le 10^5$

输入样例:

5
1 2 3 0 2

输出样例:

3

样例解释

对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出],第一笔交易可得利润 2-1 = 1,第二笔交易可得利润 2-0 = 2,共得利润 1+2 = 3。

思路

闫氏$DP$分析法:
状态表示:$f_{i,k}$,其中$k=0/1/2$

  • 集合:在前$i$天中买卖股票并且当前状态是$k$,如果$k=0$表示当前未持股,如果$k=1$表示当前持股,如果$k=2$表示当前是冷冻期
  • 属性:$Max$

状态计算:

  • 如果第$i$天未持股,那么既可以第$i-1$天未持股,也可以第$i-1$天冷冻期,即$f_{i,0}=\max\lbrace f_{i-1,0},f_{i-1,2}\rbrace$
  • 如果第$i$天持股,那么既可以第$i-1$天持股,也可以买入股票,即$f_{i,1}=\max\lbrace f_{i-1,1},f_{i-1,0}-a_i$
  • 如果第$i$天为冷冻期,那么只能第$i-1$天卖出,即$f_{i,2}=f_{i-1,1}$
  • 所以状态转移方程就是
    • $f_{i,0}=\max\lbrace f_{i-1,0},f_{i-1,2}\rbrace$
    • $f_{i,1}=\max\lbrace f_{i-1,1},f_{i-1,0}-a_i$
    • $f_{i,2}=f_{i-1,1}$

答案:

  • 由于最后持股一定不是最优解,所以答案就是$\max\lbrace f_{i,0},f_{i,2}\rbrace$

来自一只野生彩色铅笔的状态机图片:

代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int n;
int a[N];
int f[N][3];
int main () {
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    memset (f,-0x3f,sizeof (f));
    f[0][0] = 0;
    for (int i = 1;i <= n;i++) {
        f[i][0] = max (f[i - 1][0],f[i - 1][2]);
        f[i][1] = max (f[i - 1][1],f[i - 1][0] - a[i]);
        f[i][2] = f[i - 1][1] + a[i];
    }
    cout << max (f[n][0],f[n][2]) << endl;
    return 0;
}