蓝桥杯 – 第27页 – 柳婼の blog

蓝桥杯 ALGO-30 算法训练入学考试（01背包，动态规划）

问题描述
　　辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
　　如果你是辰辰，你能完成这个任务吗？
输入格式
　　第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式
　　包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
样例输入
70 3
71 100
69 1
1 2
样例输出
3
数据规模和约定
　　对于30%的数据，M <= 10；
　　对于全部的数据，M <= 100。

分析：01背包问题。对于每一个输入都有采和不采两种状态。
dp[i][j]表示对于前i个草药选择部分采且总时间不超过j小时后，草药的价值的最大值
可得dp[M][T]即是所求的解。
1.当当前输入的草药所需时间大于允许的最大时间j小时的时候，则不采，dp[i][j] = dp[i-1][j];
2.当当前输入的草药所需时间小于等于允许的最大时间小时的时候，考虑采或者不采两种状态，取能够使草药总价值最大的那个：dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + b);

#include <iostream>
using namespace std;
int dp[101][1001];
int main() {
    int t, m;
    cin >> t >> m;
    for(int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        for(int j = 1; j <= t; j++) {
            if(j >= a)
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + b);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    cout << dp[m][t];
    return 0;
}

#include <iostream>

using namespace std;

int dp[101][1001];

int main() {

int t, m;

cin >> t >> m;

for(int i = 1; i <= m; i++) {

int a, b;

cin >> a >> b;

for(int j = 1; j <= t; j++) {

if(j >= a)

dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + b);

else

dp[i][j] = dp[i-1][j];

}

cout << dp[m][t];

return 0;

}

蓝桥杯 ALGO-31 算法训练开心的金明（01背包，动态规划）

问题描述
　　金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：
“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，
肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
　　设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为 j1，j2，……，jk，则所求的总和为：
　　v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。（其中*为乘号）
　　请你帮助金明设计一个满足要求的购物单。
输入格式
　　输入文件的第1行，为两个正整数，用一个空格隔开：
　　N m
　　（其中N（<30000）表示总钱数，m（<25）为希望购买物品的个数。）
　　从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数
　　v p
　　（其中v表示该物品的价格(v<=10000)，p表示该物品的重要度(1~5)）
输出格式
　　输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<100000000）。
样例输入
1000 5
800 2
400 5
300 5
400 3
200 2
样例输出
3900
分析：01背包问题。对于每一个输入都有买和不买两种状态。
dp[i][j]表示对于前i件物品选择部分购买限定总价不超过j元后，物品的价格与重要程度乘积的总和的最大值
可得dp[m][n]即是所求的解。
1.当当前输入的物品价格大于允许的最大总价j元，则不买，dp[i][j] = dp[i-1][j];
2.当当前输入的物品体积小于等于允许的最大总价j元，考虑买或者不买两种状态，取物品的价格与重要程度乘积的总和最大的那个：dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + t);

#include <iostream>
using namespace std;
int dp[25][30000];
int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        for(int j = 1; j <= n; j++) {
            if(j >= a)
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + a * b);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    cout << dp[m][n];
    return 0;
}

#include <iostream>

using namespace std;

int dp[25][30000];

int main() {

int n, m;

cin >> n >> m;

for(int i = 1; i <= m; i++) {

int a, b;

cin >> a >> b;

for(int j = 1; j <= n; j++) {

if(j >= a)

dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + a * b);

else

dp[i][j] = dp[i-1][j];

}

cout << dp[m][n];

return 0;

}

蓝桥杯 ALGO-21 算法训练装箱问题（动态规划，01背包）

问题描述
　　有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。
　　要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入格式
　　第一行为一个整数，表示箱子容量；
　　第二行为一个整数，表示有n个物品；
　　接下来n行，每行一个整数表示这n个物品的各自体积。
输出格式
　　一个整数，表示箱子剩余空间。
样例输入
24
6
8
3
12
7
9
7
样例输出
0

分析：dp[i][j]表示前i件物品选则部分装入体积为j的背包后，背包总共所占的最大体积，
一共有n件物品，那么dp[n][v]就是前n件物品选择部分装入体积为v的背包后，背包总共占有的最大体积
1.当当前输入的物品体积大于背包容量，则不装入背包，dp[i][j] = dp[i-1][j];
2.当当前输入的物品体积小于等于背包容量，考虑装或者不装两种状态，取体积最大的那个：dp[i][j] = max(dp[i-1][j], dp[i-1][j-t] + t);

#include <iostream>
using namespace std;
int dp[31][20001];
int main() {
    int v, n;
    cin >> v >> n;
    for(int i = 1; i <= n; i++) {
        int t;
        cin >> t;
        for(int j = 1; j <= v; j++) {
            if (j >= t) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-t] + t);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout << v - dp[n][v];
    return 0;
}

#include <iostream>

using namespace std;

int dp[31][20001];

int main() {

int v, n;

cin >> v >> n;

for(int i = 1; i <= n; i++) {

int t;

cin >> t;

for(int j = 1; j <= v; j++) {

if (j >= t) {

dp[i][j] = max(dp[i-1][j], dp[i-1][j-t] + t);

} else {

dp[i][j] = dp[i-1][j];

}

cout << v - dp[n][v];

return 0;

}

蓝桥杯 ALGO-22 算法训练数的划分

问题描述
　　将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。
　　例如：n=7，k=3，下面三种分法被认为是相同的。
　　1，1，5; 1，5，1; 5，1，1;
　　问有多少种不同的分法。
输入格式
　　n，k
输出格式
　　一个整数，即不同的分法
样例输入
7 3
样例输出
4 {四种分法为：1，1，5;1，2，4;1，3，3;2，2，3;}
数据规模和约定
　　6<n<=200，2<=k<=6

分析：递归问题，step表示当前剩余的数需要分成的份数~~
把n分成k份，只需第一个数等于i，计算从i等于1一直到i等于n/k，然后把剩余的n-i分成k-1份的种类数…
front为剩余的要划分的数的前一个数，每次i从front开始一直到n/step结束，这样才能保证得到的划分方式是不递减的，才能保证不会有重复的情况产生~

#include <iostream>
using namespace std;
int cnt = 0;

void dfs(int front, int n, int step) {
    if(step == 1) {
        cnt++;
        return ;
    }
    for(int i = front; i <= n / step; i++)
        dfs(i, n - i, step - 1);
}

int main() {
    int n, k;
    cin >> n >> k;
    dfs(1, n, k);
    cout << cnt;
    return 0;
}

#include <iostream>

using namespace std;

int cnt = 0;

void dfs(int front, int n, int step) {

if(step == 1) {

cnt++;

return ;

}

for(int i = front; i <= n / step; i++)

dfs(i, n - i, step - 1);

}

int main() {

int n, k;

cin >> n >> k;

dfs(1, n, k);

cout << cnt;

return 0;

}

蓝桥杯 ADV-148 算法提高排队打水问题（贪心）

问题描述
有n个人排队到r个水龙头去打水，他们装满水桶的时间t1、t2………..tn为整数且各不相等，应如何安排他们的打水顺序才能使他们总共花费的时间最少？
输入格式
第一行n，r (n<=500,r<=75)
第二行为n个人打水所用的时间Ti (Ti<=100)；
输出格式
最少的花费时间
样例输入
3 2
1 2 3
样例输出
7
数据规模和约定
其中80%的数据保证n<=10

分析：按照时间从大到小的顺序排序后即为打水的顺序~每个人依次进入队列1…r、1…r、1…r……对于前面可以排满的且不是队列最后一排的人，每排满一行，总时间等于自身打水的时间加上前面所有人打水的时间~对于每个队列的最后一个人(或者倒数第二个人)，总时间等于自身打水的时间加上前面这一列所有人打水的时间~

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
    int n, r;
    scanf("%d %d", &n, &r);
    int *a = new int[n];
    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    sort(a, a+n);
    int ans = 0;
    int cnt = n/r;
    int index = 0;
    while(cnt--) {
        for(int j = 0; j < index; j++)
            ans += a[j];
        for(int i = 0; i < r; i++)
            ans += a[index++];
    }
    while(index < n) {
        int t = index % r;
        while(t < n) {
            ans += a[t];
            t += r;
        }
        index++;
    }
    cout << ans;
    delete [] a;
    return 0;
}

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

int main() {

int n, r;

scanf("%d %d", &n, &r);

int *a = new int[n];

for(int i = 0; i < n; i++) {

scanf("%d", &a[i]);

}

sort(a, a+n);

int ans = 0;

int cnt = n/r;

int index = 0;

while(cnt--) {

for(int j = 0; j < index; j++)

ans += a[j];

for(int i = 0; i < r; i++)

ans += a[index++];

}

while(index < n) {

int t = index % r;

while(t < n) {

ans += a[t];

t += r;

}

index++;

}

cout << ans;

delete [] a;

return 0;

}

蓝桥杯 ADV-202 算法提高最长公共子序列（动态规划）

问题描述
　　给定两个字符串，寻找这两个字串之间的最长公共子序列。
输入格式
　　输入两行，分别包含一个字符串，仅含有小写字母。
输出格式
　　最长公共子序列的长度。
样例输入
abcdgh
aedfhb
样例输出
3
样例说明
　　最长公共子序列为a，d，h。
数据规模和约定
　　字串长度1~1000。
分析：求最长公共子序列，用动态规划~只需建立一个长宽为两个字符串长度+1的二维数组~dp[i][j]表示String a的前i个字符构成的字符串和String b的前j个字符构成的字符串这两者得到的最长公共子序列的长度为dp[i][j]~~~所以第0行和第0列所有的数都为0~
根据递推公式：

Snip20160525_13

按一行一行的顺序填入数~

最后一个格子的长度就是两个字符串的最长公共子序列的长度~~

#include <iostream>
using namespace std;
int dp[1001][1001];
int main() {
    string a, b;
    cin >> a >> b;
    for(int i = 1; i <= a.length(); i++) {
        for(int j = 1; j <= b.length(); j++) {
            if(a[i-1] == b[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    cout << dp[a.length()][b.length()];
    return 0;
}

#include <iostream>

using namespace std;

int dp[1001][1001];

int main() {

string a, b;

cin >> a >> b;

for(int i = 1; i <= a.length(); i++) {

for(int j = 1; j <= b.length(); j++) {

if(a[i-1] == b[j-1])

dp[i][j] = dp[i-1][j-1] + 1;

else

dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

}

cout << dp[a.length()][b.length()];

return 0;

}