Thinking Process 两种传球方式，一个向左边一个向右边。先不考虑环的情况，直接看链。 Assumption：以第二个人为例子。他只能从第一个人和第三个人手里拿到球。Likewise, it's the same when it comes to i-th person. 状态方程 DEFINATION f[i][j]:球传了j次后到第i个人手里的方案数  EQUATION f[i][j] = f[i - 1][j - 1] + f[i + 1][j - 1] f[1][0] = 1 特别地，第一个人是从第n个人手里拿球和第二个人手里拿球，第n个人是从第n-1个人手里拿球和第1个人...

Thinking Process 初始点是(m,1)，终点是(1,n)。终点的最后一个状态只能从(1,n-1)或者(2,n)这两个坐标得来。对(i,j)这个坐标来说，由于题目只允许向上或者是向下走，所以f[i][j]=f[i][j-1]+f[i+1][j]。状态方程自然得到。 NOTICE  此题不可以使用递归来做。会超时 数组方面要开大一点，m和n都是3000的数据范围 得开long long 得取余 【一开始做的时候没取余搞得结果错了】  Code #include<iostream> using namespace std; typedef long long ll; int...

Thinking Process 1、先确定状态 f[i][j]:前i个物体能不能装满体积为j的背包? 则现在有两个选择：  选第i个物体：要看一下f[i-1][j-c[i]]，它能装下，那这个决定就可以装下 不选第i个物体：要看一下f[i-1][j] 故推出状态方程：  f[i][j] = f[i - 1][j] || f[i - 1][j - c[i]]  2、就地滚动 f[i][j]的状态都只依赖于上一行，故我们可以压缩数组的空间大小，将二维的变成一维的。 for(int i = 1;i <= n ; i ++ ) { for(int j = v; j >= c[i];j -...

processing 直接考虑最后一步：(i,j)这个位置只能从(i-1, j)和(i, j - 1)这两个位置来，所以定义状态f[i][j]:从A点到(i,j)坐标的路径条数，则推出状态转移方程：f[i][j] = f[i-1][j] + f[i][j-1]   NOTICE  points (x,y) controled by horse is 0 methods to arrive. some points in margin might be controled by horse. Specially notice it.  Code #include<iostream> ...

Thinking Process 一道动态中位数的题。 用一个大根堆的优先队列存一半较小值，用一个小根堆的优先队列存一半较大值。  如果x小于小根堆的堆顶，则意味着它应该在大根堆中 否则，则意味着它应该在小根堆中  最后一步，判断两个优先队列的大小是否相差1，如果正好相差1，哪个优先队列大，就输出哪个的top，否则的话需要修改至相差为1 Code #include<iostream> #include<queue> #include<string.h> #include<vector> using namespace std; int t, m;...

Thinking Process 这题很简单。举个例子就能知道思路。 三个果子重量分别为10、5、7.合并两次，由于第二次合并出来的值一定是10+5+7=22所以只要第一次合并出来的值小就可以了，即我们取三者之中的最小值5和7。根据这个思路就可以做出这道题。需要注意的是每一次的合并值都得纳入考虑!! first method use 2 queues to record original value and merged value.Get two minimums through compared the front value of queues. #include<iostream...

Thinking Process We ensure that current stack top is less or equal than the max value from current index to end.So what we need do is to create a list that save the max value from every i index(i = 1, 2, 3, ...) to end. like this:  for (int i = 1; i <= n; i ++) a[i] = max(b[i], a[i + 1]);  Here a...

Thinking Process Use binary search and testify every value. Assume you have known answer and check answer wheather right. If not right, how to update answer and testify it again until you verify its correctness. This is the process of this excersize. We can use difference to transfer interval update...

Thinking Process what a easy excersize! but i waste much time on input. DAMN IT! Overall, judge the length of S first. if length == 1, output it directly. otherwise, construct the tree and finally judge the type of S and output type! Code #include<stdio.h> #include<math.h> #include<st...

Thinking Process It's apparent to use recussion given the Recurssive formula.  The difficulty is how to get the minimum of n'.Thinking carefully,the formula like this:f[i]=f[i/2]+if[i] = f[i / 2] + i f[i]=f[i/2]+i%222 equals to f[i]=f[i>>1]+if[i] = f[i >> 1] + i f[i]=f[i>>1]+i%222....

Thinking Process use recurssion to calculate every digit sum. if sum < 10 return ,else calculate Code #include<stdio.h> int f(int n) { if(n < 10) return n; int sum = 0; while(n) { int t = n % 10; sum += t; n /= 10; } return f(sum); } int main() { int n; scanf("%d", &n); printf("%d", ...

Thinking Process this question is relatively easy to beginners and friendly.Method is two pointers. when the number of characters between pointer 'l' and pointer has been up to 26 different letters, update the length and only move l to plus 1. It's not necessary to move 'r' pointer because 'l'~'r' r...

thinking process use struct to store order info.  struct ty{ int l, r, c; }a[100010];  compare operator defination: a.c == b.c ? a.l < b.l : a.c < b.c  the reason why we do this is simple. Given (l,r) and let u solve the individual item value, it's inevitable to be striked that merge intervals...

thinking process i'm break down when i get this program. i don't solve this problem by myself.what i have written is other solution. i cite and refer to him to study from his code. His whole process is very simple.  three states are illegal:  While the number of times it's been seen is odd and the o...