约瑟夫问题递推法 模拟的时间开销太大 不得不回头考虑递推关系： 将编号改为从0开始,记f(n,m)为原问题的解 由于第一次遍历了0~(m-1)%n，则第二次遍历相当于将整个队伍循环左移了k位(k=m%n) 所以子问题f(n-1,m)的解循环右移k位即为原问题的解f(n,m) f(n,m)=(f(n-1,m)+m)%n #include<iostream> #include<queue> using namespace std; int getans(int n,int m){ if(n==1)return 0; else{ ...

字符串分拆 排序 比较相邻路径相同层数 输出 #include<iostream> #include<algorithm> #include<string> #include<cstring> #include<vector> using namespace std; const int maxn=10; vector <string> s[maxn];//路径 int main(){ int n; while(scanf("%d",&n)!=EOF){ memset(s,0,...

完全背包变形 （参考高赞回答） 第i轮 dp[j]:前i种物品组合成容量恰好为j的方法数 递推关系：类比完全背包（优化） dp[j]=dp[j]+dp[j-w[i]] #include<iostream> #include<cmath> using namespace std; int w[22]; int dp[1000000001]; int best(int sum,int n){ dp[0]=1;//容量为0时,初始方法数为1 for(int i=1;i<=sum;i++){//容量为0时,初始方法数为0（注意不是INF） ...

DP：M个物品划分成N份 关键：比较盘子和苹果的个数大小 dp[i][j]：i个苹果分给j个盘子 ①盘子比苹果多：一定有盘子是空的，摔掉多余空盘子即可： dp[i][j]=dp[i][i] ②盘子不比苹果多: 要么每个盘子都非空，相当于先给每个盘子放一个苹果，只用考虑剩下的i-j个苹果：dp[i-j][j] 要么至少有一个盘子空的：dp[i][j-1] #include <iostream> using namespace std; const int maxn=12; int dp[maxn][maxn];// int main(){ int m,n; while...

原题暂未找到可用ojDescriptionYou are in the world of mathematics to solve the great "Monkey Banana Problem". It states that, a monkey enters into a diamond shaped two dimensional array and can jump in any of the adjacent cells down from its current position (see figure). While moving from one cell to anothe...

原题链接DescriptionFigure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.InputYour program is to read from s...

原题链接DescriptionBefore ACM can do anything, a budget must be prepared and the necessary financial support obtained. The main income for this action comes from Irreversibly Bound Money (IBM). The idea behind is simple. Whenever some ACM member has any small money, he takes all the coins and throws the...

0-1背包变形：容量恰好用完 类比：容量：给定的总面值sum、邮票[i]的重量：面值w[i] 、价值：均为1 第i轮 dp[j]：前i张邮票凑出总面值为j的最少张数 初始状态：dp[0]=0; dp[i]=INF(0<i<=sum) 表示无法完成 递推关系：dp[j]=min(dp[j],dp[j-w[i]]+1) #include<iostream> #include<cstring> using namespace std; const int maxn=101; const int INF=0x7fffffff; int w[maxn]; i...

多重背包 每种物品有若干个,物品i的体积：w[i]、价值：v[i]、数量：amount 第i轮：dp[j]:前i个物品装进容量为j的背包所获得的最大价值 采用二进制 将同种物品组合成新的物品，化为0-1背包求解 #include<iostream> #include<string> using namespace std; const int maxn=500010; int w[maxn];//体积 int v[maxn];//价值 int dp[maxn]; int best(int sum,int n){//0-1背包（优化） for(int i=0...

原题链接题目描述设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。输入描述第一行：两个整数，M(背包容量，M<=200)和N(物品数量，N<=30)；第2..N+1行：每行二个整数Wi,Ci，表示每个物品的重量和价值。输出描述输出最大总价值。格式：“max=12”完全背包问题每种物品有无穷多个,物品i的体积：w[i]、价值：v[i]dp[i][j]:前i种物品装进容量为j的背包所获得的最大价值与0-1背包唯一区别：dp[i][j]=max...

0-1背包 每种物品只有一个,物品i的体积：w[i]、价值：v[i] dp[i][j]:前i个物品装进容量为j的背包所获得的最大价值 ① 不放第i个物品 dp[i][j]=dp[i-1][j] ② 放入第i个物品 dp[i][j]=dp[i-1][j-w[i]]+v[i] #include<iostream> using namespace std; const int maxn=1001; int w[maxn]; int v[maxn]; int dp[maxn][maxn]; int best(int sum,int n){ for(int i=0;i<=...

最长公共子序列：DP 思路：s1[i]与s2[j]是否匹配，dp[i+1][j+1]:以s[i]与s[j]为末尾匹配的最长公共序列长度， 由于要输出序列，所以得到公共子序列长度后，需要从后往前拼接 ①是：dp[i+1][j+1]=dp[i][j]+1;都往前一个字符，再匹配 ②否：dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]) s1往前一个字符，再匹配 或者 s2往前一个字符，再匹配 #include<iostream> #include<string> using namespace std; const int maxn=500...

原题链接DescriptionA subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = < x1, x2, ..., xm > another sequence Z = < z1, z2, ..., zk > is a subsequence of X if there exists a strictly increasing sequence < i1, i2, ..., ik ...

最长“山顶”子序列 DP：分别递推以s[i]开头的最长下降子序列、以s[i]结尾的最长上升子序列 #include<iostream> #include<cstring> using namespace std; const int maxn=101; int s[maxn]; int high[maxn];//上升子序列长度 int low[maxn];//下降子序列长度 int student(int n){//“山顶”子序列最大长度 fill(high,high+n,1); fill(low,low+n,1); for(in...