题目是： a^3=b^3+c^3+d^3 b<=c<=d<=a<=N 输入N 输出abcd
#include <iostream> using namespace std; int main() { int N; cin >> N; for (int a = 2; a <= N; ++a) { for (int b = 2; b < a; ++b) { for (int c = b; c < a; ++c) { for (int d = c; d < a; ++d) { if (a* a* a == b * b * b + c * c * c + d * d * d) { cout << a << " (" << b << "," << c << "," << d << ")" << endl; } } } } } return 0; }体力情商智商每隔23，28，33天出现高峰，求交集 保证(k-p)%23==0 && (k-e)%28==0 && (k-i)%33==0 跳着试 可以这样来简化： 1.先找到用第一个体力日子 2.然后23天23天的往后找找到恰好情商的日子 3.再23*28天地这样往下直到出现智商日子
#include <iostream> using namespace std; int main() { int p, e, i, d; while (cin >> p >> e >> i >> d && p != 1) { int k; for (k = d + 1; (k - p) % 23; ++k); for (; (k - e) % 28; k += 23); for (; (k - i) % 33; k += 23 * 28); cout << k - d << endl; } return 0; }12枚硬币，11真，1假 不知假币是轻还是重 现在用天平秤这些币三次 请找出假币并确定是轻还是重
输入： ABCD EFGH even ABCI EFJK up右重 ABIJ EFGH even右轻
输出： K is light
思路： 假设每一枚币是假币为轻的/为重的都试验一遍
#include <iostream> #include <cstring> using namespace std; //ABCDE FGHIJ KL char Left[3][7];//左边硬币 char Right[3][7];//右边硬币 char result[3][7];//结果 bool IsFake(char c, bool light) {//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; } 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 和else if仅接受1的情况，返回的false没用 if (IsFake(c, true)) {//假设f硬币为假且它为轻 cout << c << "is light" << endl; break; } else if (IsFake(c, false)) { cout << c << "is heavy" << endl; } } } return 0; }5*6矩阵中 按下一个按钮后其周围位置（上，下，左，右）灯都会改变及自己 给定一个矩阵的状态，现在使所有灯都熄灭
输入： 011010 100111 001001 100101 011100
输出： 按下按钮的地方 101001 110101 001011 100100 010000
分析： 按开关只能按一次
首先假设出第一行开关的状态 2^6次 那么只能通过第二行开关来影响上一行 同理第二行也只能通过第三行开关来影响 最后第五行还有灯亮着，则开始方案有问题
其实也可以开一个一维的char类型数组来节约内存 用二进制数字来计算 2^6=64
#include <iostream> #include <cstring> #include <memory> using namespace std; char oriLights[5]; char lights[5]; char result[5]; int GetBit(char c, int i) {//得知i位是0/1 return (c >> i) & 1; } void SetBit(char& c, int i, int v) {//使某一位设置为1/0 if (v) { c |= (1 << i); } else { c &= ~(1 << i); } } void FlipBit(char& c, int i) {//反转0/1 c ^= (1 << 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));//每选择一次调灯方式后都将原有灯存至调试lights内存中 for (int i = 0; i < 5; ++i) {//逐行进行调试 result[i] = switchs;//第一行存储来自外面的0~64方案，第二行的调整来参看上一行亮着的灯 for (int j = 0; j < 6; j++) {//再该行挨个位置进行翻转 if (GetBit(switchs, j)) {//如果该j位置上亮灯了则开始调灯，按第一次设计的方案先调整一编第一行的样子 if (j > 0) {//左右都按照设计方式调整，不管结果如何 FlipBit(lights[i], j - 1); } if (j < 5) { FlipBit(lights[i], j + 1); } } } if (i < 4) {//因为下一行的按钮被上一行相对应的方式调整过，所以如果上面调整则相对应下方要调整 lights[i + 1] ^= switchs;//那么下一行调整后进行一次反转 } switchs = lights[i];//第一行的调整过的灯还有亮的则存入switch } if (lights[4] == 0) { OutputResult(t, result); break; } } } return 0; }求n!的递归函数
#include <iostream> using namespace std; int Factorial(int n) { if (n == 0) { return 1; } else { return Factorial(n - 1) * n; } }要求n个国际象棋的皇后摆在n*n的棋盘上 且相互不能攻击，输出全部方案
输出结果里每一行都代表一种摆法 行里第i个数字代表第i行皇后放在第几列
输入： 4 输出： 2 4 1 3 3 1 4 2
#include <iostream> 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) {//在0~k-1行皇后已经摆好的情况下，摆第k行及其后的皇后 int i; if (k == N) {//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++) {//和已经摆好的第k个皇后的位置比较，看是否冲突 if (queenPos[j] == i || abs(queenPos[j] - i) == abs(k - j)) { break; } } if (j == k) {//当前选的位置i不冲突 queenPos[k] = i;//将第k个皇后摆在位置i NQueen(k + 1); } } }2+3 表示为+23 (2+3)*4表示为* + 2 34 (11+12)*(24+35)表示为* + 11 12 + 24 35
atof()函数将字符串形式转换为浮点类型的数字
#include <iostream> #include <cstdio> #include <cstdlib> 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() { printf("%lf", exp()); return 0; }输入为四则运算表达式 仅由 数字+-*/（）构成 结果都是整数int型
表达式是个递归的定义： 表达式 = 项±而形成 表达式=项+项-项 项 = 因子*/而形成 项=因子*因子/因子 因子 为 整数或（表达式）而形成
#include <iostream> #include <cstring> #include <cstdlib> using namespace std; int factor_values();//读入一个因子 int term_values();//读入一项 int expression_values();//读入表达式 int main() { cout << expression_values() << endl; return 0; } int expression_values() {//读入表达式 int result = term_values();//求第一项的值 bool more = true; while (more) { char op = cin.peek();//看一个字符，不取走 if (op == '+' || op == '-') { cin.get();//从输入中取走一个字符 int value = term_values(); if (op == '+') { result += value; } else { result -= value; } } else { more = false; } } return result; } int term_values() {//求一个项的值 int result = factor_values();//求第一个因子的值 while (true) { char op = cin.peek(); if (op == '*' || op == '/') { cin.get(); int value = factor_values(); if (op == '*') { result *= value; } else { result /= value; } } else { break; } } return result; } int factor_values() {//求一个因子的值 int result = 0; char c = cin.peek(); if (c == '(') {//则此为一个小的表达式 cin.get(); result = expression_values(); cin.get(); } else { while (isdigit) { result = 10 * result + c - '0'; cin.get(); c = cin.peek(); } } return result; }每次走1/2级台阶 n级台阶走法= 1.先走一级后，n-1级台阶走法 2.先走两级后，n-2级台阶走法 f(n)=f(n-1)+f(n-2) n=1
#include <iostream> using namespace std; int N; int stairs(int n) { if (n < 0) { return 0; } if (n == 0) { return 1; } return stairs(n - 1) + stairs(n - 2); } int main() { while (cin >> N) { cout << stairs(N) << endl; } return 0; }把M个同样的苹果放在N个同样的盘子里 允许有盘子空着
输入： 第一行是测试数据数目t 以后M和N
分析： i个苹果放在k个盘子里方法总数是f(i,k) k>i时，f(i,k)=f(i,i)后面多余的盘子没有用 k<=i时，总放法=有盘子为空的放法+没盘子为空的放法 f(i,k) = f(i,k-1) + f(i-k,k)
#include <iostream> using namespace std; int f(int m, int n) { if (n > m) { return f(m, m); } if (m == 0) { return 1; } if (n == 0) { return 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; }给出4个小于10的正整数 使用加减乘除运算得到24这个结果 如果可以得到24就输出yes 反之no
浮点数比较相等不能用== 只能是判断某俩个数的差小于某个值
#include <iostream> #include <cmath> using namespace std; double a[5]; #define EPS 1e-6 bool isZero(double x) { return fabs(x) >= EPS; } bool count24(double a[], int n) {//用数组a里的n个数，计算24 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-2 for (int k = 0; k < n; ++k) { if (k != i && k != j) {//剩余数放入b b[m++] = a[k]; } } b[m] = a[i] + a[j]; if (count24(b, m + 1)) { return true; } b[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[j] * a[i]; 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[j])) { b[m] = a[j] / a[i]; if (count24(b, m + 1)) { return true; } } } } return false; }输入n个整数 n<=100000 找出其中两个数他们和等于m
解法1: 首先先快排0(n*long(n)) 每个元素a[i]直接二分查找m-a[i 0(n*long(n))
解法2: 首先先快排0(n*long(n)) 设置俩个变量,i,j 看a[i]+a[j] 大于m,j-- 小于m,i++
1.设k=a[0],将k挪到适当位置,使得 比k小的元素都在k左边,比k大的元素都在k右边, 和k相等的不关心在k左右出现都可 2.把k左边的部分进行快速排序 3.把k右边的部分进行快速排序
#include <iostream> using namespace std; 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]); }//处理完后i=j QuickSort(a, s, i - 1); QuickSort(a, i + 1, e); } int a[] = { 93,27,30,2,8,12,2,8,30,89 }; 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; }i1,i2,..,in数列其中存在j,k 满足j<k且ij>ik
分治 0(n*log(n)) 1.将数组分为两半，分别求出左半边的逆序数和右半边的逆序数 2.再算有多少逆序是由左半边取一个数和右半边取一个数构成
左半边和右半边都是排好序的 则从头到尾各扫一遍就可以找出由两边各取一个数构成的逆序个数
排序后再输出, 0(n*log(n)) 用分治处理,0(n+m*long(m))
思路:把前m大的弄到数组最右边,然后对这最右边m个元素排序,再输出 关键:0(n)时间内把前m大的弄到数组最右边
方法: arrangeRight(k):把数组前k大的都弄到最右边 1.设key=a[0],将key挪到适当位置 使得比key小的元素都在key左边,使得比key大的元素都在key右边 2.选择数组的前部或后部再进行arrangeRight操作 a=k done a>k 对右边a-1个元素进行arrangeRight(k) a<k 对左边b个元素进行arrangeRight(k-a)
等腰三角形 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 寻找一条从顶部到底部的路径 使得路径上所经过的数字之和最大 每一步只能往左下或者右下走 求出最大的这个和(行数<=100)
5//行数 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
D(r,j)第r行第j个数字(r,j从1开始算) MaxSum(r,j)从D(r,j)到底边的各条路径中最佳路径的数字之和 开始求MaxSum(1,1) 将此问题便转化为一个递归问题,但这个会超时
改进: 每计算一次MaxSum(r,j)就保存起来，下次使用的时候直接取用 0(n^2)
继续改进:递归转为递推 倒着计算向上计算值,每次只取最大值
接着改进:节省空间 可以使用一维数组maxSum[100]
甚至可以直接使用D的第n行来代替一维数组
#include <iostream> #include <algorithm> #define MAX 101 using namespace std; int D[MAX][MAX]; int n; int MaxSum(int i, int j) { if (i == n) { return D[i][j]; } int x = MaxSum(i + 1, j); int y = MaxSum(i + 1, j + 1); return max(x, y) + D[i][j]; } int main() { int i, j; cin >> n; for (i = 1; i <= n; i++) { for (j = 1; j <= i; j++) { cin >> D[i][j]; } } cout << MaxSum(1, 1) << endl; return 0; } #include <iostream> #include <algorithm> using namespace std; #define MAX 101 int D[MAX][MAX]; int n; int maxSum[MAX][MAX]; int main() { cin >> n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { cin >> D[i][j]; } } for (int i = 1; i <= n; ++i) { maxSum[n][i] = D[n][i]; } for (int i = n - 1; i >= 1; --i) { for (int j = 1; j <= i; ++j) { maxSum[i][j] = max(maxSum[i + 1][j], maxSum[i + 1][j + 1]) + D[i][j]; } } cout << maxSum[1][1] << endl; } #include <iostream> #include <algorithm> using namespace std; #define MAX 101 int D[MAX][MAX]; int n; int maxSum[MAX][MAX]; 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() { int i, j; cin >> n; for (i = 1; i <= n; i++) { for (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; #define MAX 101 int D[MAX][MAX]; 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指向第n行 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]; } } cout << maxSum[1] << endl; }给出一个序列 1 7 3 5 9 4 8 在这一串序列中找出最长的从小到大排序的序列 1 3 5 8
1.找子问题 从序列最右边的那个数开始看起，称为该数列的终点 2.确定状态 子问题只和一个变量–数字位置相关 就是以ak做为终点的最长的上升子序列的长度 这种状态一共有n个 3.找出状态转移方程 maxLen(k)表示以ak作为终点的最长上升子序列的长度: 初始状态maxLen(1)=1 maxLen(k)=max{maxLen(i):1<=i<k且ai<ak且k!=1}+1 若找不到则继续往下找 maxLen(k)的值,就是在ak左边,有一个终点数值小于ak 那么ak也就能加入到原来的数组中,形成一个新的长度+1的数组
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 1010; int a[MAXN]; int maxLen[MAXN]; int main() { int N; cin >> N; for (int i = 1; i <= N; ++i) { cin >> a[i]; maxLen[i] = 1; } for (int i = 2; i <= N; ++i) {//每次求以第i个数为终点的最长上升子序列的长度 for (int j = 1; j < i; ++j) {//查看以第j个数为终点的最长上升子序列 if (a[i] > a[j]) { maxLen[i] = max(maxLen[i], maxLen[j] + 1); } } } cout << *max_element(maxLen + 1, maxLen + N + 1); return 0; }在两个序列中寻找一个子序列其先后顺序一致出现 abcfbc abfcab abcb就是
输入两个串s1,s2 设MaxLen(i,j)表示: s1左边的i个字符形成的子串,与s2左边的j个字符形成的子串 的最长公共子序列的长度 此函数就是所谓的状态
假定len1 = strlen(s1),len2 = strlen(s2) 那么题目就是要求MaxLen(len1,len2) 那么MaxLen(n,0)=0 (n=0…len1) MaxLen(0,n)=0 (n=0…len2) 递推公式: if(s[i-1]==s2[j-1])//s1最左边的字符是s1[0] MaxLen(i,j)=MaxLen(i-1,j-1)+1; else MaxLen(i,j)=Max(MaxLen(i,j-1),MaxLen(i-1,j)) 时间复杂度:0(m*n)m,n是两个字串长度
#include <iostream> #include <cstring> #include <algorithm> using namespace std; char sz1[1000]; char sz2[1000]; int maxLen[1000][1000]; int main() { while (cin >> sz1 >> sz2) { int length1 = strlen(sz1); int length2 = strlen(sz2); int nTmp; int i, j; for (i = 0; i <= length1; i++) { maxLen[i][0] = 0; } for (j = 0; j <= length2; j++) { maxLen[0][j] = 0; } for (i = 1; i <= length1; i++) { for (j = 1; j <= length2; j++) { if (sz1[i - 1] == sz2[j - 1]) { maxLen[i][j] = maxLen[i - 1][j - 1] + 1; } else { maxLen[i][j] = max(maxLen[i][j - 1], maxLen[i - 1][j]); } } } cout << maxLen[length1][length2] << endl; } return 0; }一个由1~9组成的字符串中 将M个加号插入到这个字符串中 这个sum值最小为多少？
假定字符串长度为n 添加完加号后表达式的最后一个加号添加在第i个数字后面 那么整个表达式的最小值等于前i个数字中插入m-1个加号形成的最小值 加上第i+1到第n个数字所形成的数的值
设V(m,n)表示在n个数字中插入m个加号所能形成的表达式的最小值 if m==0: V(m,n)=n个数字构成的整数 else if n<m+1: V(m,n) = ∞ else: V(m,n)=Min{V(m-1,i)+Num(i+1,n)}(i=m…n-1) Num(i,j)表示从第i个数字到第j个数字所组成的数 数字编号从1开始算 0(j-i+1)可预处理后存起来 总0(m*n^2)
场景中包括多个平台和高度不同的平台 地面是最低的平台,高度为0,长度无限 Jimmy在时刻0从高于所有平台的某处开始下落 下落速度始终为1m/s,当落在某个平台的时候可选择向左还是向右 在平台上跑动的速度也是1m/s,当跑到边缘的时候开始继续下落 每次下落的距离不能超过MAX米,不然就会摔死 求问下落到地面的最短时间?
输入: 第一行是测试数据组数t
每组测试数据第一行是四个整数: N是平台数目 X和Y是Jimmy开始下落的位置的横纵坐标 MAX是一次下落的最大高度
接下来N行,每行描述一个平台,包括三个整数: X1[i] x2[i]和H[i]
分析: 将板子从上到下从1开始编号 认为Jimmy开始从一个编号为0,长度为0的板子 假设LeftMinTime(k)表示从k号板子左端到地面最短时间 假设RightMinTime(k)表示从k号板子右端到地面最短时间
if(板子k左端正下方没有别的板子) { if(板子k的高度h(k)大于MAX) { LeftMinTime(k)=无穷; } else { LeftMinTime(k)=h(k); } } else if(板子k左端正下方的板子编号是m) { LeftMinTime(k)=h(k)-h(m)+ Min( LeftMinTime(m) + Lx(k) - Lx(m) ), RightMinTime(m) + Rx(m) - Lx(k) ); }
现在给出一个滑雪场地区域,由二维数组构成,数组中的数字代表点的高度 一个人可以从某个点滑向上下左右相邻四个点之一,且仅能高度减小 输出最长区域的长度 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 找出最长的滑雪区域25
L(i,j)表示从点(i,j)出发的最长滑行长度 一个点(i,j),如果周围没有比它低的点,L(i,j)=1 否则:L(i,j)等于(i,j)周围四个点中比(i,j)点低,且L值最大的那个点的L值,再加1 0(n^2)
解法1) "人人为我"式递推 L(i,j)表示从点(i,j)出发的最长滑行长度 一个点(i,j),如果周围没有比它低的点,L(i,j)=1 将所有点按高度从小到大排序.每个点的L值都初始化为1 从小到大遍历所有的点.经过一个点(i,j)时,用递推公式求L(i,j)
解法2) "我为人人"式递推 L(i,j)表示从点(i,j)出发的最长滑行长度 一个点(i,j),如果周围没有比它低的点,L(i,j)=1 将所有点按高度从小到大排序.每个点的L值都初始化为1 从小到大遍历所有的点.经过一个点(i,j)时,要更新他周围的,比它高的点的L值 if H(i+1,j) > H(i,j) L(i+1) = max( L(i+1,j), L(i,j)+1 )
有一个体积为40的容器 有一堆体积分别为a1,a2,a3…,an的物品 要求得到的物品的总体积为40 共有多少种不同的选法
#include <iostream> using namespace std; int a[30]; int N; int Ways(int w, int k) {//从前k种物品中选择一些,凑成体积w的做法数目 if (w == 0) { return 1; } if (k <= 0) { return 0; } return Ways(w, k - 1) + Ways(w - a[k], k - 1); //从k-1个物品中选出w体积的东西 //先选上第k个物品,从k-1个物品中选出体积为w-k体积的东西 } int main() { cin >> N; for (int i = 1; i <= N; ++i) { cin >> a[i]; } cout << Ways(40, N); return 0; } #include <iostream> using namespace std; int a[30]; int N; int Ways[40][30]; //Ways[i][j]表示从前j种物品里凑出体积i的方法数 int main() { cin >> N; memset(Ways, 0, sizeof(Ways)); for (int i = 0; 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]; } } } cout << Ways[40][N]; return 0; }有N件物品和一个容积为M的背包 第i件物品的体积w[i],价值是d[i] 求解将哪些物品装入背包可使价值总和最大
用F[i][j]表示取前i种物品,使他们总体积不超过j的最优取法取得的价值总和,求F[N][M] 边界:if ( w[1] <= j ) F[1][j] = d[1]; else f[1][j] = 0; 递归式:F[i][j] = max( F[i-1][j], F[i-1][j-w[i]]+d[i]) 取或不取第i种物品,两者选优 但这样会开很大的内存,超内存
可以使用一维数组,人人为我的递推型动归实现
有一个矩形大蛋糕,宽和高分别是整数w,h 现要将其切成m块小蛋糕 最后得到的m块小蛋糕中,最大的那块蛋糕的面积最小 输入:每行输入W,H,M 当W=H=W=0时不需要处理,表示结束
思路: 设Ways(w,h,m)表示宽为w,高为h的蛋糕,被切m刀后最大的那块蛋糕的面积最小值 题目就是要求ways(W,H,M-1) 边界条件: w * h < m + 1 : ∞ m == 0 :w*h 递推: SV为第一刀竖着切时能得到的最好结果 SH为第一刀横着切时能得到的最好结果 ways(w,h,m) = min(SV,SH) SV = min{Si, i = 1…w-1} Si = 为第一刀左边宽为i的情况下的最好结果 Si = min{ max(ways(i,h,k), ways(w-i,h,m-1-k)), k=0…m-1}
用一个二维数组存放图，G[i][j]表示节点i和节点j之间边的情况（如有无边，边方向，权值大小等）
邻接表
图中是一个城堡的地形图，编写一个程序，计算城堡一共有多少房间，最大的房间有多大。城堡被分割为m*n(m≤50,n<50)个方块，每个方块可以有0～4面墙
输入：在接下来的输入行中，每个方块用一个数字(0≤p≤50)描述。用一个数字表示方块周围的墙，1表示西墙，2表示北墙，4表示东墙，8表示南墙。每个方块用代表其周围墙的数字之和表示。城堡内墙被计算两次，方块1，1的南墙同时也是方块2，1的北墙
解题思路：
把方块看作是节点，相邻两个方块直接如果没有墙，则在方块之间连一条边，这样城堡就能转换成一个图。求房间个数，实际上就是在求图中有多少个极大连通子图。一个连通子图，往里头加任何一个图里的其他点，就会变得不连通，那么这个连通子图就是极大连通子图。对每一个房间，深度优先搜索，从而给这个房间能够到达的所有位置染色。最后统计一共用了几种颜色，以及每种颜色的数量。 #include <iostream> #include <stack> #include <cstring> using namespace std; int R, C;//R行，C列 int rooms[60][60]; int color[60][60];//方块是否被染色 int maxRoomArea = 0, roomNum = 0;//最终所求的两个终值 int roomArea;//正在探索的房间的最大面积 void Dfs(int i, int k) { if (color[i][k]) return; ++roomArea; color[i][k] == roomNum; if ((rooms[i][k] & 1) == 0) Dfs(i, k - 1);//向西走 if ((rooms[i][k] & 2) == 0) Dfs(i - 1, k);//向北 if ((rooms[i][k] & 4) == 0) Dfs(i, k + 1);//向东 if ((rooms[i][k] & 8) == 0) Dfs(i + 1, k);//向南 } int main() { cin >> R >> C; for (int i = 1; i <= R; ++i) { for (int k = 1; k <= C; ++k) { cin >> rooms[i][k]; } } memset(color, 0, sizeof(color));//走过的房间标记为1 for (int i = 1; i <= R; ++i) { for (int k = 1; k <= C; ++k) { if (!color[i][k]) {//如果是新的房间 ++roomNum; roomArea = 0; Dfs(i, k); maxRoomArea = max(roomArea, maxRoomArea); } } } cout << roomNum << endl; cout << maxRoomArea << endl; }有一个方格矩阵，矩阵边界在无穷远处。
每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；走过的格子立即塌陷无法再走第二次；只能向北，东，西三个方向走如果允许在方格矩阵上走n步(n<=20),共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同的方案。
递归思路： 从(i,j)出发，走n步的方案数，等于一下三项之和： 从(i + 1,j)出发，走 n-1 步的方案数。前提：(i + 1,j)还没走过 从(i,j + 1)出发，走 n-1 步的方案数。前提：(i,j + 1)还没走过 从(i,j - 1)出发，走 n-1 步的方案数。前提：(i,j - 1)还没走过
#include <iostream> #include <cstring> using namespace std; int visited[30][50]; int ways(int i, int j, int n) {//方案数,从ij出发，走n步一共有几种走法 if (n == 0) return 1;//走0步就一种走法，就是不走 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;//表示从这个位置退出，那么这个位置就会相当于没走过 return num; } int main() { int n; cin >> n; memset(visited, 0, sizeof(visited)); cout << ways(0, 25, n) << endl; return 0; }N个城市，编号1到N。城市间有R条单向道路。每条道路连接两个城市，有长度和过路费两个属性。Bob只有K块钱，他想从城市1走到城市N。问最短共需要走多长的路。如果到不了N，输出-1
输入： K N R S1 e1 L1 T`1
从城市1 开始深度优先遍历整个图，找到所有能到达N的走法，选一个最优的。
#include <iostream> #include <cstring> #include <vector> using namespace std; int K, N, R; //N个城市，R条路 struct Road { int d;//终点 int L;//长度 int t;//过路费 }; vector<vector<Road>> G(110); //G[i]中的i相当于是起点 int minLen; //最终的路的长度 int totalLen;//当前探索的路已经走了多长 int totalCost;//当前探索的路花费了多少钱 int visited[110];//标记当前的路是否走过 void dfs(int s) { if (s == N) { minLen = min(minLen, totalLen); 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]) {//判断是否走过 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)); totalLen = 0; minLen = 1 << 30;//好大的数 totalCost = 0; visited[1] = 1; dfs(1); if (minLen < (1 << 30)) { cout << minLen << endl; } else { cout << -1 << endl; } }结果给超时了
最优性剪枝
如果当前已经找到的最优路径长度为L，那么在继续搜索的过程中，总长度已经大于等于L的走法，就可以直接放弃，不用走到底。用midL[k][m]表示：走到城市k时走过路费为m的条件下，最优路径的长度。若在后续的搜索中，再次走到k时，如果总路费恰好为m，且此时的路径长度已经超过midL[k][m]，则不必再走下去了。 #include <iostream> #include <cstring> #include <vector> using namespace std; int K, N, R; //N个城市，R条路 struct Road { int d;//终点 int L;//长度 int t;//过路费 }; vector<vector<Road>> G(110); //G[i]中的i相当于是起点 int minL[110][10010];//minL[i][j] int minLen; //最终的路的长度 int totalLen;//当前探索的路已经走了多长 int totalCost;//当前探索的路花费了多少钱 int visited[110];//标记当前的路是否走过 void dfs(int s) { if (s == N) { minLen = min(minLen, totalLen); 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; } if (totalLen + r.L >= minL[r.d][totalCost + r.t]) { continue; } minL[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)); totalLen = 0; minLen = 1 << 30;//好大的数 totalCost = 0; visited[1] = 1; for (int i = 0; i < 110; i++) { for (int j = 0; j < 10010; j++) { minL[i][j] = 1 << 30; } } dfs(1); if (minLen < (1 << 30)) { cout << minLen << endl; } else { cout << -1 << endl; } }要制作一个体积为N兀的M层生日蛋糕，每层都是一个圆柱体。设从下往上数第i(1≤i≤M)层蛋糕是半径为Ri，高度为Hi的圆柱。当i<M时，要求Ri>Ri+1且Hi>Hi+1 由于要在蛋糕上摸奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的总面积Q最小。 令Q=S*兀 编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。（除Q外，以上所有数据皆为正整数）
#include <iostream> #include <cstring> #include <vector> using namespace std; int N, M; int minArea = 1 << 30;//最优表面积 int area = 0;//正在搭建中的蛋糕的表面积 void Dfs(int v, int n, int r, int h) //要用n层去凑体积v，最底层半径不能超过r，高度不能超过h //求出最小表面积放入minArea { if (n == 0) {//终值条件，不需要搭蛋糕了，（0，0，？，？） if (v) return; else { minArea = min(minArea, area); return; } } if (v <= 0) { return; } for (int rr = r; rr >= n; --rr) { if (n == M) { area = rr * rr; } for (int hh = h; hh >= n; --hh) { area += 2 * rr * hh; Dfs(v - rr * rr * hh, n - 1, rr - 1, hh - 1); area -= 2 * rr * hh; } } } int main() { Dfs(N, M, maxR, maxH); if (minArea == 1 << 30) { cout << 0 << endl; } else { cout << minArea << endl; } }农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位置位于点N(0≤N≤100000)，牛位于点K(0≤K≤100000)。农夫有两种移动方式：
从X移动到X-1或X+1，每次移动花费一分钟从X移动到2*X，每次移动花费一分钟假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛。
策略1·深度优先搜索：从起点出发，随机挑一个方向，能往前走就往前走（扩展），走不动了则回溯。不能走已经走过的点（要判重）。 要想求最优解，则要遍历所有走法。可以用各种手段优化，比如，若已经找到路径长度为n的解，则长度大于n的走法就不必尝试。 运算过程中需要存储路径上的节点，数量较少。用栈存节点。策略2·广度优先搜索： 给节点分层。起点是第0层。从起点最少需要n步就能到达的点属于第n层 搜索过程（节点扩展过程）： 3 2 4 6 1 5 问题解决。 扩展时，不能扩展出已经走过的节点（要判重）。 可确保找到最优解，但是因扩展出来的节点较多，且多数节点都需要保存，因此需要的存储空间较大。用队列存节点。定义一个矩阵： 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
基础广搜。先将起始位置入队列 每次从队列中拿出一个元素，扩展其相邻的四个元素放入队列（要判重），直到对头元素为终点为止。队列里的元素记录了指向父节点（上一步）的指针
队列元素：
struct { int r,c; int f;//父节点在队列中的下标 };队列不能用STL的queue或deque，要自己写。用一位数组实现，维护一个队头指针
有一个3*3的棋盘，其中有0-8共九个数字，0表示空格，其他的数字可以和0交换位置。求由初始状态到达目标状态12345678的步数最少的解。
广度优先搜索：
用队列保存待扩展的节点
从队首队取出节点，扩展出的新节点放入队尾，直到队首出现目标节点（问题的解）
框架：
Bfs() { 初始化队列; while(队列不为空且未找到目标节点) { 取队首节点扩展，并将扩展出的非重复节点放入队尾; 必要时要记住每个节点的父节点; } }关键问题：判重
新扩展出的节点如果和以前扩展出的节点相同则这个新节点就不必考虑如何判重？用合理的编码表示状态，减小存储代价：
方案一：九个int方案二：一个int方案三：状态数目一共只有9！个，即362880个，怎么会需要876543210（9）即381367044（10）个标志位呢？