Code – 第228页

蓝桥杯 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;

}

蓝桥杯 ADV-156 算法提高分分钟的碎碎念(动态规划)

问题描述
　　以前有个孩子，他分分钟都在碎碎念。不过，他的念头之间是有因果关系的。他会在本子里记录每一个念头，并用箭头画出这个念头的来源于之前的哪一个念头。翻开这个本子，你一定会被互相穿梭的箭头给搅晕，现在他希望你用程序计算出这些念头中最长的一条因果链。
　　将念头从1到n编号，念头i来源于念头from[i]，保证from[i]<i，from[i]=0表示该念头没有来源念头，只是脑袋一抽，灵光一现。
输入格式
　　第一行一个正整数n表示念头的数量
　　接下来n行依次给出from[1]，from[2]，…，from[n]
输出格式
　　共一行，一个正整数L表示最长的念头因果链中的念头数量
样例输入
8
0
1
0
3
2
4
2
4
样例输出
3
样例说明
　　最长的因果链有：
　　1->2->5 (from[5]=2,from[2]=1,from[1]=0)
　　1->2->7 (from[7]=2,from[2]=1,from[1]=0)
　　3->4->6 (from[6]=4,from[4]=3,from[3]=0)
　　3->4->8 (from[8]=4,from[4]=3,from[3]=0)
数据规模和约定
　　1<=n<=1000
分析：建立一个与from数组等长的数组dp，dp[i]表示当前序号能满足构成的最长的长度，dp[i]的值可以由dp[from[i]]+1得到~

#include <iostream>
#include <cstdio>
using namespace std;
int main() {
	int n;
	scanf("%d", &n);
	int *dp = new int[n+1];
	int *from = new int[n+1];
	for(int i = 1; i <= n; i++) {
		scanf("%d", &from[i]);
	}
	dp[0] = 0;
	int maxvalue = 0;
	for(int i = 1; i <= n; i++) {
		dp[i] = dp[from[i]] + 1;
		maxvalue = max(maxvalue, dp[i]);
	}
	cout << maxvalue;
	delete [] dp;
	delete [] a;
}

#include <iostream>

#include <cstdio>

using namespace std;

int main() {

int n;

scanf("%d", &n);

int *dp = new int[n+1];

int *from = new int[n+1];

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

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

}

dp[0] = 0;

int maxvalue = 0;

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

dp[i] = dp[from[i]] + 1;

maxvalue = max(maxvalue, dp[i]);

}

cout << maxvalue;

delete [] dp;

delete [] a;

}

蓝桥杯 ADV-136 算法提高大数加法

问题描述
　　输入两个正整数a,b，输出a+b的值。
输入格式
　　两行，第一行a，第二行b。a和b的长度均小于1000位。
输出格式
　　一行，a+b的值。
样例输入
4
2
样例输出
6

分析：用两个指针一起从后往前加两个字符串，用carry变量表示进位，如果最后还有进位就还要再加1.

include <iostream>
using namespace std;
int main() {
    string a, b;
    cin >> a >> b;
    char ans[1001];
    int p = a.length() - 1;
    int q = b.length() - 1;
    int carry = 0;
    int i = 0;
    while(p != -1 && q != -1) {
        int ta = a[p] - '0';
        int tb = b[q] - '0';
        if(ta + tb + carry >= 10) {
            ans[i++] = (char)(ta + tb + carry - 10 + '0');
             carry = 1;
        } else {
            ans[i++] = (char)(ta + tb + carry + '0');
            carry = 0;
        }
        p--;
        q--;
    }
    while(p != -1) {
        int ta = a[p] - '0';
        if(ta + carry >= 10) {
            ans[i++] = (char)(ta + carry - 10 + '0');
            carry = 1;
        } else {
            ans[i++] = (char)(ta + carry + '0');
            carry = 0;
        }
        p--;
    }
    while(q != -1) {
        int tb = b[q] - '0';
        if(tb + carry >= 10) {
            ans[i++] = (char)(tb + carry - 10 + '0');
            carry = 1;
        } else {
            ans[i++] = (char)(tb + carry + '0');
            carry = 0;
        }
        q--;
    }
    if(carry == 1) {
        ans[i] = '1';
    }
    for(; i >= 0; i--) {
        cout << ans[i];
    }
    return 0;
}

include <iostream>

using namespace std;

int main() {

string a, b;

cin >> a >> b;

char ans[1001];

int p = a.length() - 1;

int q = b.length() - 1;

int carry = 0;

int i = 0;

while(p != -1 && q != -1) {

int ta = a[p] - '0';

int tb = b[q] - '0';

if(ta + tb + carry >= 10) {

ans[i++] = (char)(ta + tb + carry - 10 + '0');

carry = 1;

} else {

ans[i++] = (char)(ta + tb + carry + '0');

carry = 0;

}

p--;

q--;

}

while(p != -1) {

int ta = a[p] - '0';

if(ta + carry >= 10) {

ans[i++] = (char)(ta + carry - 10 + '0');

carry = 1;

} else {

ans[i++] = (char)(ta + carry + '0');

carry = 0;

}

p--;

}

while(q != -1) {

int tb = b[q] - '0';

if(tb + carry >= 10) {

ans[i++] = (char)(tb + carry - 10 + '0');

carry = 1;

} else {

ans[i++] = (char)(tb + carry + '0');

carry = 0;

}

q--;

}

if(carry == 1) {

ans[i] = '1';

}

for(; i >= 0; i--) {

cout << ans[i];

}

return 0;

}