• 网站链接
  👉b站算法基础 国家精品 北京大学 郭炜-哔哩哔哩
  👉中国大学慕课程序设计与算法（二）算法基础 北京大学 郭炜

代码均由个人整理，有错误欢迎指正！

枚举

一个个试

完美立方

#include<iostream>
using namespace std;
int main()
{int N = 100;for (int a = 2; a < N; a++)for (int b = 2; b < a - 1; b++)for (int c = 2; c < b - 1; c++)for(int d=2;d<c-1;d++)if(a*a*a==b*b*b+c*c*c+d*d*d)cout<< "Cube=" << a << "," << "Triple=" << "(" << b << "," << c << "," << d << "," << ")" << endl;return 0;
}

生理周期

#include<iostream>
using namespace std;
int main()
{int p, e, i, d;int c = 0;while (cin >> p >> e >> i >> d && p!=-1){c++;int k;for (k = d + 1; (k - p) % 23; k++);for (; (k - e) % 28; k += 23);for (; (k - i) % 33; k += 23 * 28);cout << "Case " << c << ": the next triple peak occurs in " << k - d << " days" << endl;}return 0;
}

称硬币

#include<iostream>
#include<cstring>
using namespace std;
char Left[3][7];
char Right[3][7];
char result[3][7];
bool IsFake(char c, bool light);
int main()
{int t;cin >> t;while (t--){for (int i = 0; i < 3; i++)cin >> Left[i] >> Right[i] >> result[i];for (char c = 'A'; c <= 'L'; c++){if (IsFake(c, true)){cout << c << "is the counterfeit coin and it is light" << endl;break;}else if (IsFake(c, false)){cout << c << "is the counterfeit coin and it is heavy" << endl;break;}}}return 0;
}
bool IsFake(char c, bool light)
{for (int i = 0; i < 3; i++){char* pLeft, * pRight;if (light){pLeft = Left[i];pRight = Right[i];}else{pLeft = Right[i];pRight = Left[i];}switch (result[i][0]) {case'u':if (strchr(pRight, c) == NULL)return false;break;case'e':if (strchr(pLeft, c) || strchr(pRight, c)); return false;break;case'd':if (strchr(pLeft, c) == NULL)return false;break;}}return true;
}

熄灯问题

局部思想
二进制枚举

#include<iostream>
#include<string>
#include<cstring>
#include<memory>
using namespace std;
char oriLights[5];
char lights[5];
char result[5];int GetBit(char c, int i)
{return (c >> i) & 1;//右移
}
void SetBit(char &c, int i, int v)//其它位不变，第i位改成v
{if (v)c |= (1 << i);elsec &= ~(1 << i);//只有i位1，其它0；再反；再与c与，c就是第i位为0其它不变
}
void FlipBit(char& c, int i)//翻转
{c ^= (1 << i);//c的第i位翻转
}
void OutputResult(int t, char result[])
{cout << "PUZZLE #" << t << endl;for (int i = 0; i < 5; i++){for (int j = 0; j < 6; j++){cout << GetBit(result[i], j);if (j < 5)cout << ' ';}cout << endl;}
}
int main()
{int T; cin >> T;for(int t=1;t<=T;t++){for (int i = 0; i < 5; i++){for (int j = 0; j < 6; j++){int s; cin >> s;SetBit(oriLights[i], j, s);}}for (int n = 0; n < 64; n++){int switchs = n;memcpy(lights, oriLights, sizeof(oriLights));for (int i = 0; i < 5; i++){result[i] = switchs;for (int j = 0; j < 6; j++){if (GetBit(switchs, j))//是1才需要处理{if (j > 0)FlipBit(lights[i], j-1);FlipBit(lights[i], j);if (j < 5)FlipBit(lights[i], j + 1);}}if (i < 4)lights[i + 1] ^= switchs;//翻转下一行switchs = lights[i];//确定下一行开关状态}if (lights[4] == 0){OutputResult(t, result);break;}}}return 0;
}

递归

函数调用其自身

汉诺塔

#include<iostream>
using namespace std;
void Hanoi(int n, char src, char mid, char dest)//src上n个以mid为中转移到dest
{if (n == 1){cout << src << "->" << dest << endl;return;}Hanoi(n - 1, src, dest, mid);//将n-1从src到midcout << src << "->" << dest << endl;//将1个从src到destHanoi(n - 1, mid, src, dest);//将n-1从mid到destreturn;
}
int main()
{int n;cin >> n;Hanoi(n, 'A', 'B', 'C');return 0;
}

N皇后

用递归替代多重循环
可以输出所有结果

#include<iostream>
#include<cmath>
using namespace std;
int N;
int queenPos[100];
void NQueen(int k);
int main()
{cin >> N;NQueen(0);//从第0行开始摆皇后return 0;
}
void NQueen(int k)//前k-1行已经摆好
{int i;if (k == N){for (i = 0; i < N; i++)cout << queenPos[i] + 1 << ' ';cout << endl;return;}for (i = 0; i < N; i++)//尝试第k行皇后的位置{int j;for (j = 0; j < k; j++)//与前面的皇后比较位置看是否有重复{if (queenPos[j] == i || abs(queenPos[j] - i) == abs(k - j))break;}if (j == k){queenPos[k] = i;NQueen(k + 1);}}
}

逆波兰表达式

用递归解决递归形式的问题

#include<iostream>
using namespace std;
double exp()
{char s[20];cin >> s;switch (s[0]) {case'+':return exp() + exp();case'-':return exp() - exp();case'*':return exp() * exp();case'/':return exp() / exp();default:return atof(s);//字符串转浮点数break;}
}
int main()
{cout << exp() << endl;;return 0;
}

表达式求值

#include<iostream>
using namespace std;
int factor_value();
int term_value();
int expression_value();
int main()
{cout << expression_value() << endl;return 0;
}int factor_value()
{int result = 0;char c = cin.peek();if (c == '('){cin.get();result = expression_value();cin.get();}else{while (isdigit(c))//如果是数字,不知道是几位{result = 10 * result + c - '0';cin.get();c = cin.peek();}}return result;
}
int term_value()
{int result = factor_value();//求第一个因子while (true){char op = cin.peek();//读取一个字符if (op == '*' || op == '/'){cin.get();//取走一个字符int value = factor_value();if (op == '*')result *= value;elseresult /= value;}elsebreak;}return result;
}
int expression_value()
{int result = term_value();//求第一项的值bool more = true;while (more){char op = cin.peek();//读取一个字符if (op == '+' || op == '-'){cin.get();//取走一个字符int value = term_value();if (op == '+')result += value;elseresult -= value;}elsemore = false;}return result;
}

上台阶

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

放苹果

#include<iostream>
using namespace std;
int f(int m, int n)
{if (n > m)return f(m, m);if (m == 0)return 1;//没有苹果是1种放法if (n == 0)return 0;//没有盘子是0种放法return f(m, n - 1) + f(m - n, n);//有盘子为空的+没有盘子为空的
}
int main()
{int t, m, n;cin >> t;while (t--){cin >> m >> n;cout << f(m, n) << endl;}return 0;
}

算24

枚举+递归

#include<iostream>
using namespace std;
double a[5];
#define eps 1e-6
bool isZero(double x)
{return fabs(x) <= eps;
}
bool count24(double a[], int n)
{if (n == 1){if (isZero(a[0] - 24))return true;else return false;}double b[5];for (int i = 0; i < n - 1; i++)for (int j = i + 1; j < n; j++)//枚举两数组合{int m = 0;//剩下的数个数m,m=n-2for (int k = 0; k < n; k++)//然后把剩下的数放进数组bif (k != i && k != j)b[m++] = a[k];b[m] = a[i] + a[j];if (count24(b, m + 1))return true;//m+1=n-1b[m] = a[i] - a[j];if (count24(b, m + 1))return true;b[m] = a[j] - a[i];if (count24(b, m + 1))return true;b[m] = a[i] * a[j];if (count24(b, m + 1))return true;if (!isZero(a[j])){b[m] = a[i] / a[j];if (count24(b, m + 1))return true;}if (!isZero(a[i])){b[m] = a[j] / a[i];if (count24(b, m + 1))return true;}}return false;
}
int main()
{for (int i = 0; i < 4; i++){cin >> a[i];}if (count24(a, 4))cout << "YES" << endl;else cout << "NO" << endl;return 0;
}

二分

BinarySearch模板

int BinarySearch(int a[], int size, int p)
{int L = 0;int R = size - 1;while (L <= R){int mid = L + (R - L) / 2;if (p == a[mid])return mid;else if (p > a[mid])L = mid + 1;elseR = mid - 1;}return -1;
}

LowerBound模板

int LowerBound(int a[], int size, int p)
{int L = 0;int R = size - 1;int lastPos = -1;while (L <= R){int mid = L + (R - L) / 2;if (a[mid]>=p)R = mid - 1;else{lastPos = mid;L = mid + 1;}		}return lastPos;
}

单增方程求解

#include<iostream>
using namespace std;
double eps = 1e-6;
double f(double x)
{return x * x * x - 5 * x * x + 10 * x - 80;
}
int main()
{double root, x1 = 0, x2 = 100, y;root = x1 + (x2 - x1) / 2;int triedTimes = 1;y = f(root);while (fabs(y) > eps){if (y > 0)x2 = root;else x1 = root;root = x1 + (x2 - x1) / 2;y = f(root);triedTimes++;}cout << root << endl;cout << triedTimes << endl;return 0;
}

找一对数

非二分但比二分快的方法3

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{int n,m; cin >> n>>m;int a[100000];for (int i = 0; i < n; i++)cin >> a[i];sort(a, a + n);int i = 0, j = n - 1;while (i < j){if (a[i] + a[j] == m){cout << a[i] << ' ' << a[j] << endl;break;}else if (a[i] + a[j] > m)j--;else i++;}if (i == j)cout << "no ans" << endl;return 0;
}

农夫和奶牛

难点在怎么判断距离对不对

#include<iostream>
#include<algorithm>
using namespace std;
int a[100005];
int n, c;
bool judge(int dis) {int num = 1, pre = a[0];for (int i = 0; i < n; i++) {if (a[i] - pre >= dis) {num++;pre = a[i];if (num == c) {return true;}}}return false;
}
int main() {cin>>n>>c;for (int i = 0; i < n; i++) {cin>>a[i];}sort(a, a + n);int l = 0, r = 1000000000 / c;//答案在lr范围内int mid;int ans;while (l <= r) {mid = (l + r) >> 1;if (judge(mid)) {ans = mid;l = mid + 1;}else {r = mid - 1;}}cout << ans << endl;return 0;
}

分治

归并排序模板

空间O(n) 需要一个同样大小的额外空间

#include<iostream>
using namespace std;
int a[10] = { 13, 27, 19, 2, 8, 12, 2, 8, 30, 89 };
int b[10];
void Merge(int a[], int s, int m, int e, int tmp[])//s--m,m+1--e合并到tmp，且保证tmp有序，再拷回a
{int pb = 0;int p1 = s, p2 = m + 1;while (p1 <= m && p2 <= e){if (a[p1] < a[p2])tmp[pb++] = a[p1++];else tmp[pb++] = a[p2++];}while (p1 <= m)	tmp[pb++] = a[p1++];while (p2 <= e)	tmp[pb++] = a[p2++];for (int i = 0; i <= e - s ; i++)a[s + i] = tmp[i];
}
void MergeSort(int a[],int s,int e,int tmp[])//数组，开始结尾下标，中转
{if (s < e){int m = s + (e - s) / 2;MergeSort(a, s, m, tmp);MergeSort(a, m + 1, e, tmp);Merge(a, s, m, e, tmp);}
}
int main()
{int size = sizeof(a) / sizeof(int);MergeSort(a, 0, size - 1, b);for (int i = 0; i < size; i++)cout << a[i] << ' ';cout << endl;return 0;
}

快速排序模板

#include<iostream>
using namespace std;
int a[] = { 93,27,30,2,8,12,2,8,30,89 };
void swap(int& a, int& b)
{int tmp = a; a = b; b = tmp;
}
void QuickSort(int a[], int s, int e)
{if (s >= e)return;int k = a[s];int i = s, j = e;while (i < j){while (j > i && a[j] >= k)j--;swap(a[i], a[j]);while (i < j && a[i] < k)i++;swap(a[i], a[j]);}QuickSort(a, s, i - 1);QuickSort(a, i + 1, e);
}
int main()
{int size = sizeof(a) / sizeof(int);QuickSort(a, 0, size - 1);for (int i = 0; i < size; i++)cout << a[i] << ' ';cout << endl;return 0;
}

输出前m大的数

分治+快排

#include<stdlib.h>
#include<iostream>
using namespace std;
int  a[1000005]; //当数据过大时要放在函数外面防止栈溢出
int  n,m;
void  QuickSort(int  low, int  high) {int  tmp;tmp = a[low];int  l = low;int  r = high;if (l > r)return;while (l != r) {while (a[r] < tmp && l < r) r--;if (l < r) {a[l] = a[r];l++;}while (a[l] > tmp && l < r) l++;if (l < r) {a[r] = a[l];r--;}}a[l] = tmp;if (m <= l + 1) QuickSort(low, l - 1);else {QuickSort(low, l - 1);QuickSort(l + 1, high);}
}
int  main() {while (cin>>n>>m) {for (int i = 0; i < n; i++)cin >> a[i];QuickSort(0, n - 1);for (int i = 0; i < m; i++) {cout << a[i];if (i != m - 1)cout<<' ';}cout << endl;}return  0;
}

求排列的逆序数

归并
劈一半，左边数+右边数+左边比右边大的数

#include<iostream>
using namespace std;
int a[100005], tmp[100005];
long long sum;
void MergeSort(int l, int m, int r)
{int p1 = l, p2 = m + 1;int pt = l;while (p1 <= m && p2 <= r){if (a[p1] <= a[p2])tmp[pt++] = a[p1++];else{sum += m - p1 + 1;//逆序总数 tmp[pt++] = a[p2++];}}while (p1 <= m) tmp[pt++] = a[p1++]; //将剩下的直接放入 while (p2 <= r) tmp[pt++] = a[p2++]; for (int i = l; i <= r; i++)a[i] = tmp[i];//将排好的数放回 
}
void Merge_sort(int l, int r)
{if (l < r){int mid = (l + r) >> 1;Merge_sort(l, mid);//归并左边 Merge_sort(mid + 1, r);//归并右边 MergeSort(l, mid, r);//归并排序 }
}
int main()
{int n;cin >> n;for (int i = 0; i < n; i++)cin >> a[i];Merge_sort(0, n-1);cout << sum << endl;//输出逆序总数 return 0;
}

动态规划

递归转换成递推

方式	n	范围	ans	优点	缺点
递归	个参数	参数取值	递归函数返回值	直观易写	爆栈可能性高
递推	维数组	数组下标	数组元素的值	效率高 滚动数组节省空间	逆向思维

• 递推：从边界值开始逐步填充数组，相当于计算递归的逆过程
  状态 值 状态转移方程
• 动规特点：问题具有最优子结构；无后效性

数字三角形

记忆递归

记忆递归型动规程序 防重复计算超时

#include<iostream>
#include<algorithm>
using namespace std;
int D[101][101];
int n;
int maxSum[101][101];
int MaxSum(int i,int j)
{if (maxSum[i][j] != -1)return maxSum[i][j];if (i == n) maxSum[i][j] = D[i][j];else{int x = MaxSum(i + 1, j);int y = MaxSum(i + 1, j + 1);maxSum[i][j] = max(x, y) + D[i][j];}return maxSum[i][j];
}
int main()
{cin >> n;for(int i=1;i<=n;i++)for (int j = 1; j <= i; j++){cin >> D[i][j];maxSum[i][j] = -1;}cout << MaxSum(1, 1) << endl;return 0;
}

一维递推

空间优化：二维->一维，无需额外空间

#include<iostream>
#include<algorithm>
using namespace std;
int D[101][101];
int n;
int* maxSum;//设指针
int main()
{cin >> n;for(int i=1;i<=n;i++)for (int j = 1; j <= i; j++)cin >> D[i][j];maxSum = D[n];//maxSum指向D的最后一行for (int i = n - 1; i >= 1; i--)for (int j = 1; j <= i; j++)maxSum[j] = max(maxSum[j], maxSum[j + 1]) + D[i][j];//maxSum[j]对应D[n][j]cout << maxSum[1]<< endl;//D最后一行一直在改动为和return 0;
}

最长上升子序列

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int a[1010];
int maxLen[1010];
int main()
{int n; cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];maxLen[i] = 1;}for (int i = 0; i <= n; i++)//第i个数为终点的最长上升子序列长度for (int j = 1; j < i; j++)//看i左边的第j个数为终点的最长上升子序列if (a[i] > a[j])maxLen[i] = max(maxLen[i], maxLen[j] + 1);cout << *max_element(maxLen + 1, maxLen + n + 1) << endl;return 0;
}

最长公共子序列

#include<iostream>
#include<algorithm>
using namespace std;
char s1[1000], s2[1000];
int maxLen[1000][1000];
int main()
{while (cin >> s1 >> s2){int len1 = strlen(s1);int len2 = strlen(s2);for (int i = 0; i <= len1; i++)maxLen[i][0] = 0;for (int j = 0; j <= len2; j++)maxLen[0][j] = 0;for (int i = 1; i <= len1; i++)for (int j = 1; j <= len2; j++){if (s1[i - 1] == s2[j - 1])maxLen[i][j] = maxLen[i - 1][j - 1] + 1;elsemaxLen[i][j] = max(maxLen[i][j - 1], maxLen[i - 1][j]);}cout << maxLen[len1][len2] << endl;}return 0;
}

最佳加法表达式

#include<iostream>
using namespace std;
int a[1005], num[1005][1005], dp[1005][1005];//存数字串 i-j间的数 在i个数中插j个加号的表达式最小值
int main() {int n, m;while (cin>>n>>m){for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= n; i++)//预处理,计算i到j数字串组成的数字 for (int j = i ; j <= n; j++) num[i][j] = num[i][j - 1] * 10 + a[j];memset(dp, 0x3f, sizeof(dp));for (int i = 1; i <= n; i++)dp[0][i] = num[1][i];//无加号for (int i = 1; i <= m; i++)for (int j = i; j <= n; j++)for (int k = i; k <= j; k++)dp[i][j] = min(dp[i][j], dp[i - 1][k] + num[k + 1][j]);//对比递归t = min(t, V(m-1,i)+num[i+1][n]);cout << dp[m][n] << endl;}
}

Help Jimmy

#include<iostream>
using namespace std;
int t, N, X, Y, MAX;
int x1[1010], x2[1010], h[1010], LeftMinTime[1010], RightMinTime[1010];
void h_sort(int x1[], int x2[], int h[]) {for (int i = 0; i < N; i++) {for (int j = i + 1; j < N; j++) {if (h[j] > h[i]) {swap(h[i], h[j]);swap(x1[i], x1[j]);swap(x2[i], x2[j]);}}}
}
int find(int x, int y) {for (int i = 0; i < N; i++)if (x >= x1[i] && x <= x2[i])if (y > h[i] && h[i] != 0)return i;return -1;
}
void FindLeft(int i, int l)
{if (l == -1 && h[i] <= MAX)LeftMinTime[i] = h[i];else if (h[i] - h[l] <= MAX)LeftMinTime[i] = h[i] - h[l] + min(LeftMinTime[l] + x1[i] - x1[l], RightMinTime[l] + x2[l] - x1[i]);elseLeftMinTime[i] = 1000000000;
}
void FindRight(int i, int r)
{if (r == -1 && h[i] <= MAX)//板子i右端正下方没有别的板子，且高度离平面不超过maxRightMinTime[i] = h[i];else if (h[i] - h[r] <= MAX)//板子i右端正下方的板子编号r，且俩块板子的高度差小于MAXRightMinTime[i] = h[i] - h[r] + min(LeftMinTime[r] + x2[i] - x1[r], RightMinTime[r] + x2[r] - x2[i]);elseRightMinTime[i] = 1000000000;//高度超了
}
int main() {cin >> t;while (t--){cin >> N >> X >> Y >> MAX;for (int i = 0; i < N; i++)cin >> x1[i] >> x2[i] >> h[i];h_sort(x1, x2, h);//排序int firstB = find(X, Y);//找第一块板子 if (firstB == -1) {//没有答案cout << Y << endl;continue;}for (int i = N - 1; i >= 0; i--) {FindLeft(i, find(x1[i], h[i]));FindRight(i, find(x2[i], h[i]));}int minTime = Y - h[firstB] + min(LeftMinTime[firstB] + X - x1[firstB], RightMinTime[firstB] + x2[firstB] - X);cout << minTime << endl;}return 0;
}

滑雪

我为人人型

#include<iostream>
#include<algorithm>
using namespace std;
int R, C;
int h[105][105];
int L[105][105];
int to[4][2] = { 1,0,-1,0,0,1,0,-1 };
int ans = 1;
struct node {int x;int y;int high;
};
bool cmp(node a, node b) 
{return a.high < b.high;
}
void maxL(node s) 
{int x = s.x, y = s.y;for (int i = 0; i < 4; i++){int x2 = x + to[i][0], y2 = y + to[i][1];//遍历周围点if (x2 > 0 && y2 > 0 && x2 <= R && y2 <= C) {if (L[x2][y2] < L[x][y] + 1 && h[x2][y2] > h[x][y])//长度比原来点小且高度比原来高{L[x2][y2] = L[x][y] + 1;if (ans < L[x2][y2])ans = L[x2][y2];}}}
}
int main() {cin >> R >> C;int k = 0;node s[10005];for (int i = 1; i <= R; i++) {for (int j = 1; j <= C; j++) {cin >> h[i][j];k++;s[k].high = h[i][j];s[k].x = i;s[k].y = j;L[i][j] = 1;}}sort(s + 1, s + k + 1, cmp);for (int i = 1; i <= k; i++) {maxL(s[i]);}cout << ans << endl;return 0;
}

人人为我型

#include<iostream>
#include<algorithm>
using namespace std;
int R, C;
int h[105][105];
int L[105][105];
int to[4][2] = { 1,0,-1,0,0,1,0,-1 };
int ans = 1;
struct node {int x;int y;int high;
};
bool cmp(node a, node b) 
{return a.high < b.high;
}
void maxL(node s) 
{int x = s.x, y = s.y;for (int i = 0; i < 4; i++) {int x2 = x + to[i][0], y2 = y + to[i][1];if (x2 > 0 && y2 > 0 && x2 <= R && y2 <= C) {if (h[x][y] > h[x2][y2]) {L[x][y] = max(L[x2][y2] + 1, L[x][y]);ans = max(ans, L[x][y]);}}}
}
int main() 
{cin >> R >> C;int k = 0;node s[10005];for (int i = 1; i <= R; i++) {for (int j = 1; j <= C; j++) {cin >> h[i][j];k++;s[k].high = h[i][j];s[k].x = i;s[k].y = j;L[i][j] = 1;}}sort(s + 1, s + k + 1, cmp);for (int i = 1; i <= k; i++) {maxL(s[i]);}cout << ans << endl;return 0;
}

神奇的口袋

先写递归思路再逆推递推方法会简单一些

#include<iostream>
using namespace std;
int a[30], n, ways[40][30];
int main()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];ways[0][i] = 1;}ways[0][0] = 1;for(int w=1;w<=40;w++)for (int k = 1; k <= n; k++){ways[w][k] = ways[w][k - 1];if (w - a[k] >= 0)ways[w][k] += ways[w - a[k]][k - 1];//对比递归方法：w==1re1;k<=0re0; //return ways(w, k - 1) + ways(w - a[k], k - 1);}cout << ways[40][n] << endl;return 0;
}

0-1背包问题

二维空间太大&下一行的值只用到了上一行的俩值->压缩成滚动数组，从上到下，从右到左求

#include<iostream>
using namespace std;
int n, m, w[3505], d[3505];
int f[13000];//取前i种物品，总体积不超过j的最优价值总和
int main()
{cin >> m >> n;for (int i = 1; i <= n; i++)cin >> w[i] >> d[i];for (int i = 1; i <= n; i++)for (int j = m; j >= w[i]; j--)f[j] = max(f[j], f[j - w[i]] + d[i]);
//二维方法
/*for (int i = 1; i <= n; i++)for (int j = m; j >= w[i]; j--)f[i][j] = max(f[i-1][j], f[i-1][j - w[i]] + d[i]);*/cout << f[m] << endl;return 0;
}

分蛋糕

#include <iostream>
using namespace std;
const int INF = 0x3f3f3f3f;
int minS[21][21][21];//将i*j切k刀，最大面积下限
int main()
{int w, h, m;while (cin >> w >> h >> m) {if (w == 0)break;memset(minS, INF, sizeof(minS));for (int i = 1; i <= w; i++) {for (int j = 1; j <= h; j++) {for (int k = 0; k <= m - 1; k++){if (k == 0)minS[i][j][k] = i * j;//当一块蛋糕不分时else if (i * j < k + 1)minS[i][j][k] = INF;//失败设为无穷大else{for (int r = 1; r < i; r++)// 横着切for (int q = 0; q < k; q++)minS[i][j][k] = min(minS[i][j][k], max(minS[r][j][q], minS[i - r][j][k - q - 1]));//不切或者第一刀的最好结果for (int c = 1; c < j; c++)// 竖着切for (int q = 0; q < k; q++)minS[i][j][k] = min(minS[i][j][k], max(minS[i][c][q], minS[i][j - c][k - q - 1]));}}}}cout << minS[w][h][m - 1] << endl;}
}

深度优先

城堡问题

#include<iostream>
using namespace std;
int R, C;
int rooms[60][60];
int color[60][60];
int maxRoomArea = 0, roomNum = 0;
int roomArea;//当前房间面积
void Dfs(int i, int j)//从（i，j）开始探索房间
{if (color[i][j])return;roomArea++;color[i][j] = roomNum;if ((rooms[i][j] & 1) == 0)Dfs(i, j - 1);//第一位为0说明没有西墙if ((rooms[i][j] & 2) == 0)Dfs(i - 1, j);if ((rooms[i][j] & 4) == 0)Dfs(i, j + 1);if ((rooms[i][j] & 8) == 0)Dfs(i + 1, j);
}
int main()
{cin >> R >> C;for (int i = 1; i <= R; i++)for (int j = 1; j <= C; j++)cin >> rooms[i][j];memset(color, 0, sizeof(color));for(int i=1;i<=R;i++)for (int j = 1; j <= C; j++){if (!color[i][j])//找到了新房间{roomNum++;roomArea = 0;Dfs(i, j);maxRoomArea = max(roomArea, maxRoomArea);}}cout << roomNum << endl;cout << maxRoomArea << endl;return 0;
}

踩方格

#include<iostream>
using namespace std;
int visited[30][50];
int ways(int i, int j, int n)//ij出发走n步的方案数
{if (n == 0)return 1;visited[i][j] = 1;int num = 0;if (!visited[i][j - 1])num += ways(i, j - 1, n - 1);if (!visited[i][j + 1])num += ways(i, j + 1, n - 1);if (!visited[i + 1][j])num += ways(i + 1, j, n - 1);visited[i][j] = 0;//ij对别的点是没走过的，要清0return num;
}
int main()
{int n;cin >> n;memset(visited, 0, sizeof(visited));cout << ways(0, 25, n) << endl;return 0;
}

寻路问题

剪枝

#include<iostream>
#include<vector>
using namespace std;
int K, N, R;
struct Road
{int d, L, t;//终点，长度，价格
};
vector<vector<Road>>G(110);//i是起点
int minLen=1<<30;//目前最佳路径长度
int totalLen;//正在探索的路径长度
int totalCost;//正在探索的路已经花了多少钱
int visited[110];
int minL[110][100010];//1到城市i花了j的情况下的minLen
void dfs(int s)
{if (s == N)//走到终点{minLen = min(totalLen, minLen);return;}for (int i = 0; i < G[s].size(); i++){Road r = G[s][i];if (totalCost + r.t > K)continue;if (!visited[r.d]){if (totalLen + r.L >= minLen)continue;//剪枝，已经超过min就直接试下一种方法if (totalLen + r.L >= minL[r.d][totalCost + r.t])continue;//记录中间结果的剪枝elseminL[r.d][totalCost + r.t] = totalLen + r.L;totalLen += r.L;totalCost += r.t;visited[r.d] = 1;dfs(r.d);visited[r.d] = 0;totalLen -= r.L;totalCost -= r.t;}}
}
int main()
{cin >> K >> N >> R;for (int i = 0; i < R; i++){int s;Road r;cin >> s >> r.d >> r.L >> r.t;if (s != r.d){G[s].push_back(r);}}memset(visited, 0, sizeof(visited));visited[1] = 1;for (int i = 0; i < 110; i++)for (int j = 0; j < 10010; j++)minL[i][j] = 1 << 30;dfs(1);//从1开始搜索if (minLen < (1 << 30))cout << minLen << endl;elsecout << -1 << endl;return 0;
}

生日蛋糕

dfs本质还是枚举
剪枝分为最优性剪枝和可行性剪枝

#include <iostream>
using namespace std;
int area, N, M, minArea;
void dfs(int v, int n, int r, int h)//n层凑体积v，半径<=r，高<=h
{if (n == 0){if (v == 0) //层数和体积都满足条件minArea = min(minArea, area);return; //不管体积满不满足，层数到了就不能继续递归}if (area + 2 * v / r > minArea)return;  //剪枝1：area+剩余表面积的最小值 超过最优解for (int R = r; R >= n; R--)//剪枝2：半径和高度至少等于层数for (int H = h; H >= n; H--){if (v < R * R * H)continue;//剪枝3：剩余的体积最大到不了还缺的体积if (n == M)area = R * R + 2 * R * H;     //如果是最底层elsearea += 2 * R * H;dfs(v - R * R * H, n - 1, R - 1, H - 1);area -= 2 * R * H;}
}
int main()
{cin >> N >> M;minArea = 1 << 30;dfs(N, M, sqrt(N) + 1, N + 1);  //因为v=r*r*h,所以半径最大为根号N,同理高最大为N,为避免出现不可知的错误所以+1if (minArea == 1 << 30)cout << 0 << endl;elsecout << minArea << endl;return 0;
}

广度优先

抓住这头牛

#include<iostream>
#include<queue>
using namespace std;
int N, K;
const int MAXN = 100000;
int visited[MAXN + 10];
struct Step {int x;//位置int steps;//起点到x需要的步数Step(int xx, int s) :x(xx), steps(s) {}
};
queue<Step>q;
int main()
{cin >> N >> K;memset(visited, 0, sizeof(visited));q.push(Step(N, 0));//放农夫起始位置visited[N] = 1;while (!q.empty()){Step s = q.front();if (s.x == K)//找到目标{cout << s.steps << endl;return 0;}if (s.x - 1 >= 0 && !visited[s.x - 1])//左边有位置且没走过{q.push(Step(s.x - 1, s.steps + 1));visited[s.x - 1] = 1;}if (s.x + 1 <= MAXN && !visited[s.x + 1]){q.push(Step(s.x + 1, s.steps + 1));visited[s.x + 1] = 1;}if (s.x * 2 <= MAXN && !visited[s.x * 2]){q.push(Step(s.x * 2, s.steps + 1));visited[s.x * 2] = 1;}q.pop();}return 0;
}

迷宫问题

#include<iostream>
using namespace std;
int a[5][5];
int dis[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
struct node
{
public:int x, y, pre;
}q[30];
int head = 0, tail = 0;
int visit[5][5];
void bfs()
{q[0].x = 0;	q[0].y = 0;	q[0].pre = -1;//起始位置的父节点设-1tail += 1;visit[0][0] = 1;while (head < tail){for (int i = 0; i < 4; i++){int x = q[head].x + dis[i][0];//遍历上下左右四个位置int y = q[head].y + dis[i][1];if (x > -1 && x < 5 && y > -1 && y < 5 && !a[x][y] && !visit[x][y])//xy均在范围内且能走且未被搜索过{q[tail].x = x;q[tail].y = y;q[tail].pre = head;visit[x][y] = 1;tail++;if (x == 4 && y == 4){tail--; return;//到终点了}}}head++;}
}
void print(node que)
{if (que.pre == -1)cout << "(" << que.x << ", " << que.y << ")" << endl;else {print(q[que.pre]);cout << "(" << que.x << ", " << que.y << ")" << endl;}
}
int main()
{for (int i = 0; i < 5; i++) {for (int j = 0; j < 5; j++) {cin >> a[i][j];}}bfs();print(q[tail]);return 0;
}

八数码问题

7种方法求解八数码问题yqw9999

贪心

只按某种指标选取最优

圣诞老人的礼物

如果糖果只能整箱拿，则不可使用贪心算法

#include<iostream>
#include<algorithm>
using namespace std;
struct Candy
{int v, w;bool operator<(const Candy& c){return double(v) / w - double(c.v) / c.w > 1e-6;}
}candies[110];
int main()
{int n, w;cin >> n >> w;for (int i = 0; i < n; i++)cin >> candies[i].v >> candies[i].w;sort(candies, candies + n);int totalW = 0;double totalV = 0;for (int i = 0; i < n; i++){if (totalW + candies[i].w <= w){totalW += candies[i].w;totalV += candies[i].v;}else{totalV += candies[i].v * double(w - totalW) / candies[i].w;break;}}cout << totalV << endl;return 0;
}

电影节

#include<iostream>
#include<algorithm>
using namespace std;
struct Time
{int s;int e;bool operator<(const Time& t){return t.e > e;}
}T[100];
int main()
{int t; cin >> t;while (t != 0){for (int i = 0; i < t; i++){cin >> T[i].s >> T[i].e;}sort(T, T + t);int time = T[0].e;int ans = 1;for (int i = 1; i < t; i++){if (T[i].s >= time){ans++;time = T[i].e;}}cout << ans << endl;cin >> t;}return 0;
}

Stall Reservations

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
struct Cow
{int a, b;int No;bool operator<(const Cow& c)const{return a < c.a;}
}cows[50100];
int pos[50100];
struct Stall
{int end;int No;bool operator<(const Stall& s)const{return end > s.end;}Stall(int e, int n) :end(e), No(n) {}
};
int main()
{int n;cin >> n;for (int i = 0; i < n; i++){cin >> cows[i].a >> cows[i].b;cows[i].No = i;}sort(cows, cows + n);//按开始时间从小到大排序int total = 0;priority_queue<Stall>pq;for (int i = 0; i < n; i++){if (pq.empty()){total++;pq.push(Stall(cows[i].b, total));pos[cows[i].No] = total;}else{Stall st = pq.top();//挑结束时间最早的出来if (st.end < cows[i].a)//最早结束时间小于下一只牛的开始时间{pq.pop();//修改最早时间pos[cows[i].No] = st.No;pq.push(Stall(cows[i].b, st.No));}else{total++;pq.push(Stall(cows[i].b, total));pos[cows[i].No] = total;}}}cout << total << endl;for (int i = 0; i < n; i++)cout << pos[i] << endl;return 0;
}

Radar Installation

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
struct node
{int x;int y;double x1, x2;bool operator <(const node& n){return x1 < n.x1;}
}N[1005];
int main()
{int n, d;cin >> n >> d;int Case = 1;while (n != 0){int flag = 0;for (int i = 0; i < n; i++){double x,y,x1,x2;cin >> x >> y;N[i].x = x;	N[i].y = y;if (d * d * 1.0 - y * y < 0){flag = 1;break;}x1 = x - sqrt(d * d * 1.0 - y * y);x2 = x + sqrt(d * d * 1.0 - y * y);N[i].x1 = x1;N[i].x2 = x2;}if (flag){cout << "Case " << Case << ': ' << -1 << endl;continue;}sort(N, N + n);int ans = 1;int firstNoCovered = 0;double head=N[0].x1, tail=N[0].x2;for (int i = 1; i < n; i++){if (N[i].x1 <= tail&&N[i].x1>=head){if (N[i].x2 < tail)tail = N[i].x2;}else{ans++;head = N[i].x1;tail = N[i].x2;firstNoCovered = i;}}cout << "Case " << Case << ": " << ans << endl;cin >> n >> d;Case++;}return 0;
}

钓鱼

#include<iostream>
#include<queue>
using namespace std;
int Time[105];
struct lake
{int num;int lose;bool operator<(const lake& a)const{return num < a.num;}
}Lake[30];
int main()
{int n, h;cin >> n >> h;h = h * 60 / 5;for (int i = 1; i <= n; i++)cin >> Lake[i].num;for (int i = 1; i <= n; i++)cin >> Lake[i].lose;for (int i = 1; i <= n - 1; i++)cin >> Time[i + 1];int ans = 0;priority_queue<lake>q;for (int i = 1; i <= n; i++){int sum = 0;while (!q.empty())q.pop();for (int j = 1; j <= i; j++)q.push(Lake[j]);int t = 0;for (int j = 1; j <= i; j++)t += Time[j];for (int j = 0; j < h - t; j++){lake L = q.top();q.pop();if (L.num > 0)sum += L.num;L.num -= L.lose;q.push(L);}if (sum > ans)ans = sum;}cout << ans << endl;return 0;
}