/* dp[i][j]表示s[i]~s[j]的字符串 状态转移方程： dp[i][j] = dp[i - 1][j - 1] + 1, s[i] == s[j] dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]), s[i] != s[j] 边界： dp[i][0] = 0, 1 <= i <= m dp[0][j] = 0, 1 <= j <= n */ #include <algorithm> #include <cstdio> #include <cstring> using namespac...

/* 状态转移方程 sum[i] = max{1, sum[j] + 1} i < j and A[i] > A[j] 边界 sum[i] = A[i] (i = 1, 2, ... n) */ #include <algorithm> #include <cstdio> #include <iostream> using namespace std; const int N = 1000; int A[N], sum[N]; int main() { int n; while (~scanf("%d", &n)) ...

思路： 动态规划：正反两次运用LIS求出以每一个点结尾的从前往后最长递增子序列 以每一个结点结尾的从后往前最长递增子序列 当最大时，记作，表示剩下的同学排成合唱队形最多的人数则有为当前状态下最少需要出列的同学人数（因为i这个位置被重复计算了一次，故需要+1） 代码： /* LIS最长递增子序列 状态方程： dp[i] = max{dp[i], dp[j] + 1} j <= i && A[j] < A[i] 边界： dp[i] = 1(1 <= i <= n) */ #include <algorithm> #include <io...

/* 状态转移方程： dp[i] = max{dp[i], dp[j] + 1} j <= i && A[j] >= A[i] 边界: dp[i] = 1 */ #include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int maxn = 26; int A[maxn], dp[maxn]; int main(){ int k; scanf("%d", &k); for(int ...

动态规划问题 思路： 与裴波那契数列、爬楼梯等问题解法一样状态转移方程：边界： #include using namespace std; typedef long long LL; const int N = 21; LL dp[N]; int main(){ int n; scanf("%d", &n); dp[0] = dp[1] = 1; for(int i = 2; i <= n; i++){ dp[i] = dp[i - 1] + dp[i - 2]; } printf("%lld\n", dp[n...

设f(n)表示走法随阶梯数量n变化的函数找规律：1级阶梯f(1) = 1种走法2级阶梯f(2) = 2种走法3级阶梯f(3) = f(2) + f(1) = 3种走法4级阶梯f(4) = f(3) + f(2) = 5种走法...n级阶梯f(n) = f(n - 1) + f(n - 2)种走法 #include <iostream> #include <cstdio> using namespace std; typedef long long ll; ll f[100];//用long long存储上楼方式总数，避免数据溢出 int main(){ ...

题目所给用例输入有误，以输入用例描述为准：每组测试数据占1行，包括一个正整数b(1 <= b <= 92)，改为 1 92#include <algorithm> #include <cstdio> #include <iostream> #include <vector> #include <string> using namespace std; //输入棋盘边长n,返回所有合法的放置 vector<string> res; bool isValid(vector<string>& bo...

回溯算法模板 result = [] void backtrack(路径,选择列表) if 满足结束条件 result.add(路径) return for 选择 in 选择列表 do 做选择 backtrack(路径,选择列表) 撤销选择AC代码 #include <algorithm> #include <cstdio> using namespace std; const int maxn = 21; int n;//n代表不同的物品的数目 int ans = 0...

#include <algorithm> #include <iostream> #include <queue> #include <string> #include <map> using namespace std; int n;//n字符串长度 map <string, int> inq; struct Node{ string str; int step; }; queue<Node> q; //判断字符串是否存在连续的2012 bool judge(string str){ ...

#include <iostream> #include <cstdio> using namespace std; int main(){ int n, x, y, z;//n火鸡数、xyz原价格中间三位 while(~scanf("%d", &n)){ scanf("%d %d %d", &x, &y, &z); int tot, f = 0;//tot原价格、f标记是否存在能够整除火鸡数n的价格 //这里选择从9枚举到1是为了第一次输出就是最高价格 fo...

解法1：三重循环 #include <iostream> #include <cstdio> using namespace std; int main(){ int a, b, c; for(a = 1; a <= 9; a++) for(b = 1; b <= 9; b++) for(c = 0; c <= 9; c++){ int x = a * 100 + b * 10 + c; int y = b * 100 + c * 1...

解法1 #include <algorithm> #include <cstdio> #include <cmath> #include <iostream> using namespace std; int main(){ int n, x, y, z; while(~scanf("%d", &n)){ for(x = 0; x <= 20; x++) for(y = 0; y <= 33; y++) for(z = 0; z <=...

①弗洛伊德算法 #include <bits/stdc++.h> using namespace std; int n, m;//n城市个数、m道路数 const int MAXV = 105; //大数结构体 struct bign{ int d[150], len; bign(){ memset(d, 0, sizeof(d)); len = 0; } }; //输出大数 void print(bign a){ int len = min(a.len, 5) - 1;//MOD 100000 while(...

Dijkstra算法 ①对跨越两个阵营的边只保留单向边 #include <algorithm> #include <cstdio> #include <iostream> using namespace std; const int MAXV = 1010; const int INF = 1e9; int n, m;//n城市数、m道路数 int camp[MAXV];//记录阵营 int G[MAXV][MAXV]; int d[MAXV]; bool vis[MAXV] = {false}; void init(){ fill(camp,...