c++动态规划类算法编程汇总(一)背包问题(可重复|不可重复|最小)|回溯法

悠悠 2021-11-27 02:34 240阅读 0赞

动态规划(dynamic programming)是[运筹学][Link 1]的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初[美国][Link 2]数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，**把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解**，创立了解决这类过程优化问题的新方法——动态规划。

编程中一些问题可以归到动态规划的范畴。

[c++动态规划类算法编程汇总(一)背包问题|回溯法 ][c_]

[c++动态规划类算法编程汇总(二)全排列| O(n)排序 | manacher法 ][c_ O_n_ _ manacher_]

[c++策略类O(n)编程问题汇总(扑克的顺子|约瑟夫环|整数1出现的次数|股票最大利润) ][c_O_n_1_]

**目录**

一、棋盘走法

1.1 试题

1.2 思路

1.3 输入输出

1.4 最终解法

二、最小距离的点

2.1 题干

2.2 分析

2.3 解答

三、字符串的最小公因数

3.1 题干

3.2 分析

3.3 答案

3.4 相关知识

四、和为sum的解法数（背包问题）

4.1 不可重复取的背包问题

4.2 解析

4.3 答案

4.4 可重复取的背包问题

4.5 区别及联系

4.5 最小选取次数的背包

五、更改时钟

5.1 常规解法

5.2 简单解法

六、字符矩阵中找到字符串

6.1 解法

6.2 其他人答案

七、机器人走棋盘

八、游泳池水

--------------------

# 一、棋盘走法 #

当前棋盘的走法与其他位置走法有一个构成关系，因此是动态规划问题。

[https://www.nowcoder.com/profile/368591124/test/25288703/377286\#summary][https_www.nowcoder.com_profile_368591124_test_25288703_377286_summary]

## 1.1 试题 ##

初始位置在左下角(0,0)，目的地在左上角(x,y)。需要绕过n个位置。只能向上或者向右走。有多少种走法？

输入

第一行 x,y,n (0<x<=30, 0<y<=30, 0<=n<= 20) ,n表示需要绕过的点的数量
 接下来有n行, 表示boss们的坐标(0<xi<= x, 0<yi<=y，不会和小虾位置重合)
 x1, y1
 x2, y2
 ...
 xn,yn (0<x<=30, 0<y<=30, 0<=n<= 20) 表示x,y目的地坐标,n 表示需要绕过的点的数量（ n <= 20）

输出 走法的种数

//链接：https://www.nowcoder.com/questionTerminal/a71f3bd890734201986cd1e171807d30
 //来源：牛客网
 
 #include<iostream>
 using namespace std;
 
 int main() {
 int x, y, n;
 cin >> x >> y >> n;
 long long int dp[30 + 1][30 + 1] = {0};
 for (int i = 0; i < n; i++) {
 int x, y;
 cin >> x >> y;
 dp[x][y] = -1;
 }
 for (int i = 0;i <= x;i ++) dp[i][0] = 1;
 for (int j = 0;j <= y;j ++) dp[0][j] = 1;
 for (int i = 1; i <= x; i++) {
 for (int j = 1; j <= y; j++) {
 if (dp[i][j] == -1) continue;
 if (dp[i - 1][j] != -1) dp[i][j] += dp[i - 1][j];
 if (dp[i][j - 1] != -1) dp[i][j] += dp[i][j - 1];
 }
 }
 cout << dp[x][y] << endl;
 return 0;
 }

## 1.2 思路 ##

需要弄明白一个东西，如果只能向上或者向右走，则当前位置可能由左边或者下面来，则到当前位置的方法数是左边或者下面棋盘格的方法数的和。如果行为i，列为j，则dp\[i\]\[j\]表示当前的方法数，则dp\[i\]\[j\]=dp\[i-1\]\[j\]+dp\[i\]\[j-1\]

*  墙壁上的只有一种走法，因此方法数只能为1(左边墙只可能从下面来，与下面保持一致)method\[0\]\[idx\_y\]=method\[0\]\[idx\_y-1\];
 *  任意一个节点的走法为其左边与下面节点走法的和dp\[i\]\[j\]=dp\[i-1\]\[j\]+dp\[i\]\[j-1\]
 *  如果当前为-1则表示不能经过此格if(method\[idx\_x\]\[idx\_y\]==-1)continue;

## 1.3 输入输出 ##

iostram与iostram.h的区别，前者为c++的编译器可以编译的。带.h的头文件表示c语言进行编译。

\#include<iostream>

输入：

int x, y, n;
 cin >> x >> y >> n;
 long long int dp[30 + 1][30 + 1] = {0};
 for (int i = 0; i < n; i++) {
 int x, y;
 cin >> x >> y;
 dp[x][y] = -1;
 }

输出：

cout << dp[x][y] << endl;

## 1.4 最终解法 ##

注意left method与right method需要用long long int初始化

注意method\[31\]\[31\]是将method中所有的元素均设置为0；

#include<iostream>
 using namespace std;
 
 int main(){
 int x,y,n;
 long long int method[31][31]={0};
 //输入与鲁棒性测试
 cin>>x>>y>>n;
 if(x<0||x>30||y<0||y>30||(x+1)*(y+1)<n)return 1;
 for(int idx=0;idx<n;idx++){
 int x_i,y_i;
 cin>>x_i>>y_i;
 if(x_i<0||x_i>30||y_i<0||y_i>30)return 2;
 method[x_i][y_i]=-1;
 }
 //门的位置的方法数与墙的位置的方法数
 if(method[0][0]!=-1)method[0][0]=1;
 for(int idx_x=1;idx_x<=x;idx_x++){
 method[idx_x][0]=method[idx_x-1][0];
 }
 for(int idx_y=1;idx_y<=y;idx_y++){
 method[0][idx_y]=method[0][idx_y-1];
 }
 //当前方法数为其他走法方法数的和
 for(int idx_x=1;idx_x<=x;idx_x++){
 for(int idx_y=1;idx_y<=y;idx_y++){
 if(method[idx_x][idx_y]==-1)continue;
 long long int left_method=(method[idx_x-1][idx_y]==-1)?0:method[idx_x-1][idx_y];
 long long int down_method=(method[idx_x][idx_y-1]==-1)?0:method[idx_x][idx_y-1];
 method[idx_x][idx_y]=left_method+down_method;
 }
 }
 cout<<method[x][y]<<endl;
 
 return 0;
 }

//上面方法开辟了太多内存，不可行，下面用<vector>头文件的方法运行。
 #include<iostream>
 #include<vector>
 using namespace std;
 
 int main(){
 	int x;int y; int n;
 	cin >> x >> y>>n ;
 	vector<long long int> sub_methods(y+1, 0);
 	vector<vector<long long int>>methods(x + 1, sub_methods);
 	methods[0][0] = 1;
 	for (int idx = 0; idx < n; idx++){
 		int buffer_x, buffer_y;
 		cin >> buffer_x >> buffer_y;
 		methods[buffer_x][buffer_y] = -1;
 	}
 
 	for (int idx = 1; idx <= x; idx++){
 		methods[idx][0] = methods[idx-1][0];
 	}
 	for (int idx = 1; idx <= y; idx++){
 		methods[0][idx] = methods[0][idx-1];
 	}
 
 	for (int idx_x = 1; idx_x <= x; idx_x++){
 		for (int idx_y = 1; idx_y <= y; idx_y++){
 			if (methods[idx_x][idx_y] != -1){
 				methods[idx_x][idx_y] = methods[idx_x][idx_y] + methods[idx_x][idx_y];
 				long long int left_method = (methods[idx_x - 1][idx_y] == -1) ? 0 : methods[idx_x - 1][idx_y];
 				long long int down_method = (methods[idx_x][idx_y - 1] == -1) ? 0 : methods[idx_x][idx_y - 1];
 				methods[idx_x][idx_y] = left_method + down_method;
 			}
 			
 		}
 	}
 	cout << methods[x][y]<<endl;
 	int end; cin >> end;
 	return 0;
 }

# 二、最小距离的点 #

严格而言，不是动态规划类问题。用到投影的方法简化问题。

## 2.1 题干 ##

[https://www.nowcoder.com/question/next?pid=17091533&qid=501354&tid=25319553][https_www.nowcoder.com_question_next_pid_17091533_qid_501354_tid_25319553]

n×n的网格中，n<100, 房子是1，空地是0.。中转站到所有房子距离最小，返回距离。无法修建返回-1.

输入
    4
    0 1 1 0
    1 1 0 1
    0 0 1 0
    0 0 0 0
    
    输出
    8
    
    示例2
    输入
    4
    1 1 1 1
    1 1 1 1
    1 1 1 1
    1 1 1 1
    
    输出
    -1

## 2.2 分析 ##

距离为横向距离和纵向距离的和。不如投影到x轴和y轴上，算相应的坐标点与投影的距离和。

投影：

int location[100][100];
 int cast_x[100]={0};
 int cast_y[100]={0};
 for(int idx_x=0;idx_x<n;idx_x++){
 for(int idx_y=0;idx_y<n;idx_y++){
 cin>>location[idx_x][idx_y];
 if(location[idx_x][idx_y]==1){
 cast_x[idx_x]++;
 cast_y[idx_y]++;
 }
 }
 }

注意，abs函数求绝对值，还有

## 2.3 解答 ##

#include<iostream>
 #include<stdlib.h>
 using namespace std;
 
 int main(){
 int n;
 cin>>n;
 if(n>100)return 1;
 int location[100][100];
 int cast_x[100]={0};
 int cast_y[100]={0};
 for(int idx_x=0;idx_x<n;idx_x++){
 for(int idx_y=0;idx_y<n;idx_y++){
 cin>>location[idx_x][idx_y];
 if(location[idx_x][idx_y]==1){
 cast_x[idx_x]++;
 cast_y[idx_y]++;
 }
 }
 }
 int min_distance=100*100*100;
 //算出每一点的距离，取最小的
 for(int idx_x=0;idx_x<n;idx_x++){
 for(int idx_y=0;idx_y<n;idx_y++){
 if(location[idx_x][idx_y]==0){
 int distance=0;
 for(int cast_idx=0;cast_idx<n;cast_idx++){
 distance=distance+cast_x[cast_idx]*abs(cast_idx-idx_x);
 distance=distance+cast_y[cast_idx]*abs(cast_idx-idx_y);
 }
 min_distance=(min_distance<distance)?min_distance:distance;
 }
 }
 }
 if(min_distance==100*100*100)cout<<-1<<endl;
 else cout<<min_distance<<endl;
 
 return 0;
 }

# 三、字符串的最小公因数 #

非动态规划类问题，属于字符串中简单的题，用到遍历。

## 3.1 题干 ##

来源：力扣（LeetCode）这题我在做shopee后端笔试时候遇到。  
链接：https://leetcode-cn.com/problems/greatest-common-divisor-of-strings

对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。

返回字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。

示例 1：

输入：str1 = "ABCABC", str2 = "ABC"  
输出："ABC"

示例 2：

输入：str1 = "ABABAB", str2 = "ABAB"  
输出："AB"

示例 3：

输入：str1 = "LEET", str2 = "CODE"  
输出：""

对于整个程序而言，输入 ：ABCABC ABC，输出：ABC

cin会自动读入。

## 3.2 分析 ##

对于字符串的题经常遇到，所以必须清楚知道c++的头文件才能更好的做。

一般情况下，leetcode与牛客网的编译器是只给函数接口，但是实际情况下，需要编出整个main函数。因此需要熟知相应的编写方法。

## 3.3 答案 ##

答案全部通过，注意string头文件也需要using namespace std；才可以

#include<iostream>
 #include<string>
 #include<vector>
 using namespace std;
 int main(){
 string str_1,str_2;
 cin>>str_1>>str_2;
 
 int m=str_1.length();
 int n=str_2.length();
 vector<int> tmp;
 tmp.push_back(n);
 
 for(int i=n/2;i>=1;i--){
 if(n%i==0&&m%i==0)tmp.push_back(i);
 }
 
 for(auto it:tmp){ // for(int it:tmp){
 string ss=str_2.substr(0,it);
 string A,B;
 for(int k=0;k<n/it;k++){
 A+=ss;
 }
 for(int k=0;k<m/it;k++){
 B+=ss;
 }
 if(A==str_2 && B==str_1){
 cout<< ss;break;
 }
 }
 
 //cout<<str_1<<str_2;
 return 0;
 }

leet code答案

class Solution {
 public:
 	string gcdOfStrings(string str1, string str2) {
 		int str1_len = str1.length();
 		int str2_len = str2.length();
 		vector<int> gcd_num;
 
 		int min_len = (str1_len<str2_len) ? str1_len : str2_len;
 		for (int len = min_len; len>0; len--){
 			if (str1_len%len == 0 && str2_len%len == 0)gcd_num.push_back(len);
 		}
 
 		for (int gcd : gcd_num){
 			string sub_string = str2.substr(0, gcd);
 			string str_A, str_B;
 			for (int idx = 0; idx < str1_len / gcd; idx++){
 				str_A += sub_string;
 			}
 			for (int idx = 0; idx < str2_len / gcd; idx++){
 				str_B += sub_string;
 			}
 			if (str_A == str1&&str_B == str2)return sub_string;
 		}
 		string empty;
 		return empty;
 	}
 };

封装起来也可以：

#include<string>
 #include<vector>
 #include<iostream>
 using namespace std;
 
 class Solution {
 public:
 	string gcdOfStrings(string str1, string str2) {
 		int str1_len = str1.length();
 		int str2_len = str2.length();
 		vector<int> gcd_num;
 
 		int min_len = (str1_len<str2_len) ? str1_len : str2_len;
 		for (int len = min_len; len>0; len--){
 			if (str1_len%len == 0 && str2_len%len == 0)gcd_num.push_back(len);
 		}
 
 		for (int gcd : gcd_num){
 			string sub_string = str2.substr(0, gcd);
 			string str_A, str_B;
 			for (int idx = 0; idx < str1_len / gcd; idx++){
 				str_A += sub_string;
 			}
 			for (int idx = 0; idx < str2_len / gcd; idx++){
 				str_B += sub_string;
 			}
 			if (str_A == str1&&str_B == str2)return sub_string;
 		}
 		string empty;
 		return empty;
 	}
 };
 
 int main(){
 	string str1, str2;
 	cin >> str1 >> str2;
 	string out_str;
 	Solution solution_1;
 	out_str = solution_1.gcdOfStrings(str1, str2);
 	cout << out_str;
 }

## 3.4 相关知识 ##

**vector的遍历**

在vector名为tmp中，如何遍历？这种看上去更像是python的遍历。(python中很多简便的语法是从c++中引申过来的)

直接 for(auto it : tmp)即可表示it遍历了tmp中的所有元素，非常简便。也可以for( int it:tmp)更简便，也可以。这点语法更类似于用it表示tmp中元素的个数，然后完成循环。循环的因子是int。此应用必须熟练掌握，非常简便。

for(auto it:tmp)\{ //  for(int it:tmp)\{

**string的函数**

用string头文件对string进行操作非常简便。

例如python中的 直接+操作。还有str\_1.length();

for(int k=0;k<n/it;k++){
 A+=ss;
 }
 for(int k=0;k<m/it;k++){
 B+=ss;
 }

**节省运算的遍历**

这点可以不用，但是运用起来节省了大量的运行时间。本可以直接进行遍历。但是按照文中的方法，先将n

int min_len=(str1_len<str2_len)?str1_len:str2_len;
 for(;min_len>0;min_len-- ){
 
 }

# 四、和为sum的解法数（背包问题） #

[https://www.nowcoder.com/questionTerminal/7f24eb7266ce4b0792ce8721d6259800][https_www.nowcoder.com_questionTerminal_7f24eb7266ce4b0792ce8721d6259800]

背包的问题是典型的动态规划问题。用递归相对简单，但是不要用递归，因为递归开销过大。

典型的背包问题。注意！4.1与4.4中题干不一样，导致动态规划的转移矩阵不一样！先解出两道题，然后4.5中对比两道题的差异与转移矩阵的不同。

## 4.1 不可重复取的背包问题 ##

给定一个有n个正整数的数组A和一个整数sum**,求选择数组A中部分数字**和为sum的方案数。  
当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。

输入形式 n sum，第二行是这n个数

例如 ：

5 15
    10 5 2 3 5
    
    输出4
    用例:
    761 891 149 991 852 699 902 670 515 2 859 951 867 365 521 43 883 121 471 431 41 273 961 831 468 337 90 311 931 217 719 986 361 309 168 794 986 52 541 458 10 608 613 951 601 174 173 710 862 852 759 369 120 113 460 780 137 608 207 239 46 340 570 134 428 838 508 949 517 188 879 393 487 526 50 963 766 210 467 238 11 614 412 707 834 388 361 859 527 619 81 103 775 292 828 85 88 265 649 362 985 226 619 291 348 238 682 168 204 775 587 947 306 731 916 286 398 105 624 497 355 989 180 323 461 531 99 364 618 412 670 407 310 723 654 618 141 559 90 509 504 335 664 760 393 160 761 837 151 118 465 966 201 515 877 86 499 979 847 27 712 860 212 957 510 966 269 203 485 377 515 790 458 820 982 26 230 100 330 926 341 23 220 331 263 217 717 258 621 305 476 698 26 374 911 464 247 585 890 910 765 524 423 641 83 316 536 481 831 692 541 319 94 460 643 245 584 290 594 287 59 47 304 997 180 664 818 238 581 691 567 824 655 380 603 934 658 743 889 527 923 626 457 325 792 617 246 260 317 342 274 597 829 975 101 664 166 221 917 22 24 174 778 308 212 566 680 382 528 114 515 586 298 148 245 902 332 485 234 608 946 510 178 812 109 133 652 991 824 181 758 863 483 329 727 118 733 971 293 993 759 781 125 151 606 631 334 973 879 923 821 929 462 382 682 440 862 348 966 657 676 455 908 467 648 633 749 234 564 494 597 477 986 641 446 531 239 424 705 429 401 609 114 180 980 586 812 861 95 169 43 331 589 128 216 507 305 676 186 666 445 535 961 948 715 621 819 965 202 282 285 891 375 369 127 651 53 843 185 967 878 97 379 340 357 607 326 353 525 141 822 339 816 447 938 278 73 43 280 419 116 590 722 607 240 1 312 787 353 160 258 503 694 649 594 903 648 933 39 809 548 434 376 668 720 184 585 611 344 125 628 650 383 505 298 929 835 192 776 961 12 141 435 227 142 824 361 699 986 322 152 643 284 199 41 474 831 705 854 775 544 965 969 328 345 974 854 661 596 829 863 160 482 615 154 990 138 617 97 788 32 999 860 546 353 615 399 847 772 707 1 534 740 583 609 191 786 498 473 834 995 844 502 324 600 64 787 613 906 835 990 304 645 702 885 995 79 202 380 531 751 657 580 12 408 710 25 317 465 678 102 198 595 91 209 872 239 34 443 6 165 573 633 604 241 80 194 770 146 263 460 974 620 917 565 434 932 687 304 622 691 259 412 713 422 770 636 462 601 437 1 362 981 997 358 145 341 274 269 47 78 686 359 614 157 13 822 95 877 410 312 608 964 198 179 13 928 247 953 964 286 662 553 70 803 427 32 920 625 332 588 237 451 739 158 480 102 819 103 51 463 177 953 240 195 232 728 1000 161 822 958 519 70 252 470 526 94 931 345 348 225 285 768 481 697 584 892 540 501 700 841 66 202 705 526 391 370 745 899 671 656 703 815 380 152 184 720 806 32 483 569 821 971 531 392 353 625 793 173 531 499 62 816 795 170 270 659 190 289 136 386 410 284 756 24 884 874 261 973 731 262 942 571 968 735 18 319 65 180 295 391 401 498 557 593 866 330 681 693 277 345 212 454 955 356 269 429 262 891 161 662 29 55 730 930 792 445 266 940 366 949 296 257 268 263 532 305 170 524 1000 46 420 175 27 206 268 939 957 921 348 948 231 340
    对应输出应该为:
    47531834288203496

## 4.2 解析 ##

[https://www.cnblogs.com/wuyepeng/p/9672154.html][https_www.cnblogs.com_wuyepeng_p_9672154.html]

**核心思想**：设计一个bag\[n+1\] 其中有n个非0值（第一个值为0，但只能用一次） ,bag中每取前 i 个值能构成sum的方法数为 method\[i\]\[sum\] , 并且则  method\[i\]\[sum\]=method\[i-1\]\[sum\] + method\[i\]\[sum- bag\[i\]\]

**思路为**：背包当前和为sum的方法method\[i\]\[sum\]，是下面两种情况的和：

*  method\[n-1\]\[sum-bag\[n\]\],包含当前bag\[n\]，和为sum，等价于，和为sum减去bag\[n\] ，同时不包含bag\[n\] ,的方法数目。
 *  method\[n-1\]\[sum\]，不包含当前bag\[n\]，和为sum

用动态规划，类似01背包问题，

*  f（n, sum ）表示前i 个数中和为 sum 的方案数， 则 若sum >= bag\[n\],  f （ n ，sum） = f（n -1， sum）+ f （n - 1，sum - bag\[n\] ）;（这里转换矩阵的转换关系需要搞清楚，具体在后面4.5中分许，对于不同的问题，转换矩阵可能不一样，比如这个问题转换矩阵第二项是 f （n - 1，sum - bag\[n\] ））上一行n-1行的sum-bag\[n\]项，但是对于一些其他的背包问题，转换项为 f （n ，sum - bag\[n\] ））是本行的sum-bag\[n\]项
 *  否则， f （n ，sum - bag\[n\] ）不存在，  f （ n ，sum） = f（n -1， sum）。

可优化地方：由于二维数组中，第i行 只与第 i - 1 行有关，所有我们若从 最后一列 开始更新数组，则可用一维数组来保存先前状态。注意，要用long long int型，不然存不下。  
![20190728134222128.png][]

vector<long long int> s(sum + 1, 0);
 	s[0] = 1;
 	vector<vector<long long int>> res(n + 1, s);

*  通过此步确保最左边一列全是1，表示和为0的时候，一个都不取，必有一种方法。最上面一行全是0，表示0个元素，任何都构不成。
 *  但是0行0列需要为1，因为直观理解就是和为0，一个都不取，必有一种方法。
 *  另一个角度理解，行0列0值为1的方法是：为了转移矩阵考虑，和为sum-bag\[n\]的时候，必有一种方法，所以此项有必要为1

相关要注意的语法：

* 在初始化一维向量的时候，第一个表示维度，第二个表示向量中所有数字均初始化为此值。比如
 * vector<long long int> s(sum + 1, 0); 将sum+1个数初始化为0.
 * 也可以看作把后面的copy n份。vector<vector<long long int>> res(n + 1, s);比如这个是把s变量拷贝了n+1份

## 4.3 答案 ##

但是这个答案并不好，通过数量只是75%

#include<iostream>
 #include<vector>
 using namespace std;
 
 int main(){
 int n;int sum;
 cin>>n>>sum;
 vector<long long int> v(n);
 
 for(int idx=0;idx<n;idx++){
 cin>>v[idx];
 }
 
 vector<long long int> s(sum+1,0);
 s[0]=1;
 vector<vector<long long int>> res(n+1,s);
 
 for(int i=1;i<=n;i++){
 for (int j=1;j<=sum;j++){
 if(j>=v[i-1])
 res[i][j]=res[i-1][j]+res[i-1][j-v[i-1]];
 else
 res[i][j]=res[i-1][j];
 }
 }
 
 cout<<res[n][sum]<<endl;
 return 0;
 
 }

## 4.4 可重复取的背包问题 ##

2019.9.4  OJ：

[https://www.nowcoder.com/questionTerminal/f0605c09c4ab4b019bbfd6ef79130478?answerType=1&f=discussion][https_www.nowcoder.com_questionTerminal_f0605c09c4ab4b019bbfd6ef79130478_answerType_1_f_discussion]

有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱(n <= 100000)，有多少中组合可以组成n分钱？要求方法数溢出的话，方法数等于%(1e9+7时候的方法数)

写出动态规划转移矩阵：

*  method\[index\]\[sum\]= method\[index-1\]\[sum\]+ method\[index\]\[sum-bag\[index\]\]
 *  method矩阵\[index\]\[sum\]表示，和为sum时候，背包中含有bag\[index\]的时候，的方法数
 *  它由两项相加组成，一项是：method\[index-1\]\[sum\]，不含bag\[index\]的时候的方法数，
 *  另一项是：method\[index\]\[sum-bag\[index\]\]，和为sum-bag\[index\]的时候，包含bag\[index\]的时候的方法数。

即转换矩阵为： method\[index\]\[sum\]= method\[index-1\]\[sum\]+ method\[index\]\[sum-bag\[index\]\]

这种方法能否做到不重不漏？

* 比如sum为2，bag中0个2的时候，方法数为：method\[index-1\]\[sum=2\]=1,
 * 比如sum为2，bag中1个2的时候，方法数为：method\[index\]\[sum-2\]=1,
 * 这样，sum为2，所有的方法数为0个2加上1个2，method\[index\]\[sum=2\]=1+1=2
 * 比如sum为4，bag中有<=2个2的时候，方法数为：method\[index\]\[sum-2\]=method\[index\]\[sum=2\]+dp\[index-1\]\[sum\]=3,即0个2，1个2，2个2的方法数目
 * 推广一下，method\[index-1\]\[sum\]为一个2都不含的时候的方法数，method\[index\]\[sum-2\]为2比和为sum-2的时候多一个2的方法数目。其背包中2的数量并没有重复。
 * 第一项method\[index-1\]\[sum\]为不含2的时候的方法数，method\[index\]\[sum-2\]为2的个数比和为sum-2时候的2的个数多一个2的时候的方法数，做到了不重不漏。

<table> 
 <tbody> 
 <tr> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.6673in;"> index </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.6673in;"> bag </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.6673in;"> 0 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.6673in;"> 1 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:1.0715in;"> 2 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:1.0534in;"> 3 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:1.2312in;"> 。。。 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.5in;"> sum </td> 
 </tr> 
 <tr> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.6673in;"> &nbsp; </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.6673in;"> &nbsp; </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.6673in;"> 0 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.6673in;"> 0 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:1.0715in;"> 0 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:1.0534in;"> 0 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:1.2312in;"> 0 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.5in;"> 0 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.6673in;"> 0 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.6673in;"> 1 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.6673in;"> 1 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.6673in;"> 0+1 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:1.0715in;"> 0+1 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:1.0534in;"> 0+1 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:1.2312in;"> &nbsp; </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.5in;"> &nbsp; </td> 
 </tr> 
 <tr> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.6673in;"> 1 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.6673in;"> 2 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.6673in;"> 1 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.6673in;"> 1+0 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:1.0909in;"> 1+1（0个2有1中，1个2有两种） </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:1.0729in;"> 1+1（0个2有1种，1个2有1种） </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:1.2506in;"> a+b(0个2有 dp[idx-1][sum]种，n个2有dp[idx][sum-2]种) </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.5in;"> &nbsp; </td> 
 </tr> 
 <tr> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.6673in;"> 2 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.6673in;"> 5 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.6673in;"> 1 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.6673in;"> 1+0 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:1.0715in;"> &nbsp; </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:1.0534in;"> &nbsp; </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:1.2312in;"> &nbsp; </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.5in;"> &nbsp; </td> 
 </tr> 
 <tr> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.6673in;"> 3 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.6673in;"> 10 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.6673in;"> 1 </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.6673in;"> &nbsp; </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:1.0715in;"> &nbsp; </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:1.0534in;"> &nbsp; </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:1.2312in;"> &nbsp; </td> 
 <td style="border-color:#a3a3a3;vertical-align:top;width:.5in;"> &nbsp; </td> 
 </tr> 
 </tbody> 
</table>

#include<iostream>
 #include<vector>
 using namespace std;
 
 int main(){
 
 	int num; cin >> num;
 	vector<int> coin_values = { 0, 1, 2, 5, 10 };//1-1,2-2,3-5,4-10
 	vector<int> each_row(num + 1, 0);
 	vector<vector<int>> dp(5, each_row);//row 0-sum,row-1-1,row-2-2...
 	dp[0][0] = 0;
 	for (int idx = 0; idx <= 4; idx++){
 		dp[idx][0] = 1;
 	}
 	for (int idx_coin = 1; idx_coin <= 4; idx_coin++){
 		int coin_value = coin_values[idx_coin];
 		for (int idx_sum = 1; idx_sum <= num; idx_sum++){
 			dp[idx_coin][idx_sum] += dp[idx_coin - 1][idx_sum]%(1000000007);
 			dp[idx_coin][idx_sum] = dp[idx_coin][idx_sum] % (1000000007);
 			if (idx_sum - coin_value >= 0){
 				dp[idx_coin][idx_sum] += dp[idx_coin][idx_sum - coin_value] % (1000000007);
 				dp[idx_coin][idx_sum] = dp[idx_coin][idx_sum] % (1000000007);
 				//dp[idx_coin][idx_sum] += dp[idx_coin][idx_sum - coin_value];
 			}
 
 		}
 	}
 	cout << dp[4][num] << endl;
 	int end; cin >> end;
 	return 0;
 }

## 4.5 区别及联系 ##

看到这两个背包问题，一个可以重复选取元素，一个不可重复选取元素，元素只能选取一次。

**对于不能重复选取元素的转移矩阵：**

*  每个元素只能选一次，
 *  所以情况只包含，包含此元素bag\[n\]，和不包含此元素bag\[n\]
 *  因此转移矩阵需要从不包含bag\[n\]的一行过来，method\[index\]\[sum\]= method\[index-1\]\[sum\]+ method\[index-1\]\[sum-bag\[index\]\]

**对于不能重复选取元素的转移矩阵：**

*  每个元素可以选多次，
 *  情况包含包含此元素，多次的情况
 *  所以转移矩阵可以自上一行n-1过来，可以从自己行n行过来method\[index\]\[sum\]= method\[index-1\]\[sum\]+ method\[index\]\[sum-bag\[index\]\]

## 4.5 最小选取次数的背包 ##

*  N个元素，一共有S元，必须将S元花光
 *  下面一行是N个价格，
 *  输出花完S最少的选择数，选择互斥，不可重复选择，如果花不完，则输出-1

输入:
    5 7
    1 2 3 4 5
    输出2(选择3,4两个)

思路及解析：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70][]

类似于前面的背包问题，但是需要更改的是转移矩阵

*  矩阵中存储的值是获得相应的和的最小的组合的元素个数
 *  元素不能重复选取，则必然是idx行是从idx-1行来获取方案，且是最小值
 *  如果sum=bag\[idx\]则，方案数量只可能为1
 *  如果idx行和为sum，idx-1行和为sum的方案之一必然与idx-1行相同
 *  idx行的和为sum的组合的个数是idx-1行的和为sum-bag\[idx\]的方案加上1
 *  最终转移函数为：method\[idx\]\[sum\]=min(method\[idx-1\]\[sum\] , method\[idx-1\]\[sum-bag\[idx\]\]+1)

最终程序：

#include<iostream>
 #include<vector>
 #include<cstdio>
 #include<set>
 #include<string>
 #include<algorithm>
 using namespace std;
 
 int main(){
 	int num, sum; cin >> num >> sum;
 	vector<int> cost(num);
 	for (int idx = 0; idx < num; idx++){
 		cin>>cost[idx];
 	}
 
 	vector<long long int>each_row(sum + 1, 0);
 	vector<vector<long long int>> methods(num + 1, each_row);
 	for (int idx = 1; idx <= num; idx++){
 		int current_cost = cost[idx-1];
 		for (int idx_sum = 1; idx_sum <= sum; idx_sum++){
 			bool exist = false;
 			if (idx_sum - current_cost == 0){
 				methods[idx][idx_sum] = 1;
 				continue;
 			}//只看当前一场即可花完全部钱
 			//需要看多场的情况，如果之前看的加上现在这场等于sum
 			else if (idx_sum - current_cost > 0 && methods[idx - 1][idx_sum - current_cost] != 0){
 				methods[idx][idx_sum] = methods[idx - 1][idx_sum - current_cost] + 1;
 				exist = true;
 			}//如果前面已经存在
 			if (methods[idx - 1][idx_sum] != 0){
 				if (!exist)methods[idx][idx_sum] = methods[idx - 1][idx_sum];
 				else{
 					methods[idx][idx_sum] = min(methods[idx - 1][idx_sum], methods[idx][idx_sum]);
 				}
 			}
 		}
 	}
 	if (methods[num][sum] == 0){
 		cout << -1 << endl;
 	}
 	else{
 		cout << methods[num][sum] << endl;
 	}
 
 	//int end; cin >> end;
 	return 0;
 }

# 五、更改时钟 #

简单的编程题。不涉及动态规划。

## 5.1 常规解法 ##

输入一个错误的时钟时间，输出一个正确的最小的时钟时间。

输入例子1:
    2
    19:90:23
    23:59:59
    输出例子1:
    19:00:23
    23:59:59

可以用string来解：

#include<iostream>
 #include<vector>
 #include<string>
 using namespace std;
 
 int main(){
 	int num_strings;
 	cin >> num_strings;
 	vector<string> time_strings;
 	for (int idx = 0; idx < num_strings; idx++){
 		string string_buffer;
 		cin >> string_buffer;
 		time_strings.push_back(string_buffer);
 	}
 
 	for (int idx = 0; idx < num_strings; idx++){
 		// hour
 		if (time_strings[idx][0]>'2'){
 			time_strings[idx][0] = '0';
 		}
 		else if (time_strings[idx][0] == '2'){
 			if (time_strings[idx][1] > '3'){
 				time_strings[idx][0] = '0';
 			}
 		}
 		// minutes
 		if (time_strings[idx][3] > '5'){
 			time_strings[idx][3] = '0';
 		}
 
 		// second
 		if (time_strings[idx][6] > '5'){
 			time_strings[idx][6] = '0';
 		}
 	}
 
 	for (int idx = 0; idx < num_strings; idx++)
 		cout << time_strings[idx] << endl;
 
 
 	//int end; cin >> end;
 	return 0;
 }

## 5.2 简单解法 ##

通过这个解法，可以很好的节省时间，并且便于理解。

#include<stdio.h>
 using namespace std;
 int main(){
 	int T, H, M, S;
 	scanf("%d", &T);
 	while (T--){
 		scanf("%d:%d:%d", &H, &M, &S);
 		if (H >= 24)
 			H %= 10;
 		if (M >= 60)
 			M %= 10;
 		if (S >= 60)
 			S %= 10;
 		printf("%02d:%02d:%02d\n", H, M, S);
 	}
 	return 0;
 }

两点可以注意，

*  while(T--)可以实现从1到T一共T次的循环
 *  0开头的数也可以用scanf的%d读入数字之中
 *  输出可以用%02d即开始的位数补0，然后一共有两位
 *  printf("%02d:%02d:%02d\\n",155,10,3);这个语句输出是155:10:03

# **六、字符矩阵中找到字符串** #

[https://www.nowcoder.com/questionTerminal/8fb1e165abcb4b709d5a2f0ba759d0a6][https_www.nowcoder.com_questionTerminal_8fb1e165abcb4b709d5a2f0ba759d0a6]

一定要仔细审题，是右方，下方，和右下方。这种审题不清就会导致没时间做。

字符迷阵是一种经典的智力游戏。玩家需要在给定的矩形的字符迷阵中寻找特定的单词。

在这题的规则中，单词是如下规定的：

*  1. 在字符迷阵中选取一个字符作为单词的开头； 
 *  2. 选取右方、下方、或右下45度方向作为单词的延伸方向； 
 *  3. 以开头的字符，以选定的延伸方向，把连续得到的若干字符拼接在一起，则称为一个单词。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70 1][]

输入例子1:
    3
    10 10
    AAAAAADROW
    WORDBBBBBB
    OCCCWCCCCC
    RFFFFOFFFF
    DHHHHHRHHH
    ZWZVVVVDID
    ZOZVXXDKIR
    ZRZVXRXKIO
    ZDZVOXXKIW
    ZZZWXXXKIK
    WORD
    3 3
    AAA
    AAA
    AAA
    AA
    5 8
    WORDSWOR
    ORDSWORD
    RDSWORDS
    DSWORDSW
    SWORDSWO
    SWORD
    
    
    输出例子1:
    4
    16
    5

## 6.1 解法 ##

有耐心可以编出来。

#include<iostream>
 #include<vector>
 #include<string>
 using namespace std;
 int find_string_solutions(string find_string, vector<string>string_matrix, int x_loc, int y_loc){
 	int string_length = find_string.size();
 	int row_size = string_matrix.size();
 	int col_size = string_matrix[0].size();
 	int solutions = 0;
 	int idx = 0;
 	// down
 	for (idx = 0; idx < string_length; idx++){
 		if (x_loc + string_length > row_size)break;
 		if (string_matrix[x_loc + idx][y_loc] != find_string[idx])break;
 	}
 	if (idx == string_length)solutions++;
 	// right
 	for (idx = 0; idx < string_length; idx++){
 		if (y_loc + string_length > col_size)break;
 		if (string_matrix[x_loc][y_loc + idx] != find_string[idx])break;
 	}
 	if (idx == string_length)solutions++;
 	//right down
 	for (idx = 0; idx < string_length; idx++){
 		if (y_loc + string_length > col_size || x_loc + string_length > row_size)break;
 		if (string_matrix[x_loc + idx][y_loc + idx] != find_string[idx])break;
 	}
 	if (idx == string_length)solutions++;
 	return solutions;
 }
 int main(){
 	int times;
 	cin >> times;
 	for (int idx = 0; idx < times; idx++){
 		vector<string> string_matrix;
 		int size_x, size_y;
 		cin >> size_x >> size_y;
 		string current_string;
 		for (int idx_x = 0; idx_x < size_x; idx_x++){
 			cin >> current_string;
 			string_matrix.push_back(current_string);
 		}
 		string find_string;
 		cin >> find_string;
 
 		int methods = 0;
 		for (int x_loc = 0; x_loc < string_matrix.size(); x_loc++){
 			for (int y_loc = 0; y_loc <string_matrix[0].size(); y_loc++){
 				methods += find_string_solutions(find_string, string_matrix, x_loc, y_loc);
 			}
 		}
 		cout << methods << endl;
 	}
 
 	//int end; cin >> end;
 	return 0;
 
 }

## 6.2 其他人答案 ##

思路类似

#include <iostream>
 #include <string>
 #include <vector>
 using namespace std;
 
 int main()
 {
 	int T, n, m;
 	cin >> T;
 	int tmp;
 	vector<int> vCount;
 	for (int i = 0; i < T; i++)
 	{
 		cin >> n >> m;
 		vector<string> v(n);
 		for (int j = 0; j < n; j++)
 		{
 			cin >> v[j];
 		}
 		string s;
 		cin >> s;
 		int len = s.size();
 		int ind, row, col;
 		int count = 0;
 		for (int j = 0; j < n; j++)
 		{
 			for (int k = 0; k < m; k++)
 			{
 				row = j; col = k; ind = 0;
 				while (row < n && ind < len && v[row][col] == s[ind])
 				{
 					ind++;
 					row++;
 				}
 
 				if (ind == len)
 				{
 					count++;
 				}
 				row = j; col = k; ind = 0;
 				while (col < m && ind < len && v[row][col] == s[ind])
 				{
 					ind++;
 					col++;
 				}
 				if (ind == len)
 				{
 					count++;
 				}
 				row = j; col = k; ind = 0;
 				while (row < n && col < m && ind < len && v[row][col] == s[ind])
 				{
 					ind++;
 					row++;
 					col++;
 				}
 				if (ind == len)
 				{
 					count++;
 				}
 			}
 		}
 		vCount.push_back(count);
 	}
 	for (int i = 0; i < T; i++)
 	{
 		cout << vCount[i] << endl;
 	}
 	return 0;
 }

# 七、机器人走棋盘 #

[https://www.nowcoder.com/practice/6e5207314b5241fb83f2329e89fdecc8?tpId=13&tqId=11219&tPage=4&rp=4&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking][https_www.nowcoder.com_practice_6e5207314b5241fb83f2329e89fdecc8_tpId_13_tqId_11219_tPage_4_rp_4_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

我们的方法可能不是最简方案：需要注意的是，moving中需要加入一个判断，以免影响0，0的判断。

class Solution {
 public:
 	bool if_less_than_threshold(int threshold,int row, int col){
 		int sum=0;
 		while (row){
 			sum += row % 10;
 			row = row / 10;
 		}
 		while (col){
 			sum += col % 10;
 			col = col / 10;
 		}
 		if (sum <= threshold)return true;
 		else return false;
 	}
 
 	void moving(int cur_row,int cur_col,int rows,int cols,vector<vector<bool>> & reached,int threshold){
 		if (!if_less_than_threshold(threshold,cur_row, cur_col))return;
 		reached[cur_row][cur_col] = true;
 
 		//up,down
 		if (cur_row + 1 < rows && reached[cur_row + 1][cur_col] == false && if_less_than_threshold(threshold,cur_row + 1, cur_col ))
 			moving(cur_row + 1, cur_col, rows, cols, reached, threshold);
 		if (cur_row - 1 >=0 && reached[cur_row - 1][cur_col] == false && if_less_than_threshold(threshold,cur_row - 1, cur_col))
 			moving(cur_row - 1, cur_col, rows, cols, reached, threshold);
 		// left,right
 		if (cur_col + 1 < cols && reached[cur_row][cur_col + 1] == false && if_less_than_threshold(threshold,cur_row, cur_col + 1))
 			moving(cur_row , cur_col+1, rows, cols, reached, threshold);
 		if (cur_col - 1 >=0 && reached[cur_row][cur_col - 1] == false && if_less_than_threshold(threshold,cur_row, cur_col - 1))
 			moving(cur_row , cur_col-1, rows, cols, reached, threshold);
 	}
 
 	int movingCount(int threshold, int rows, int cols)
 	{
 		vector<bool> col(cols, false);
 		vector<vector<bool>> reached(rows, col);
 if (if_less_than_threshold(threshold,0, 0))
 moving(0, 0, rows, cols, reached, threshold);
 		
 		int methods = 0;
 		for (auto reach_vector : reached){
 			for (auto if_reach : reach_vector){
 				if (if_reach == true)
 					methods++;
 			}
 		}
 		return methods;
 	}
 };

# 八、游泳池水 #

可以用类似于辗转相减法来实现。

*  最大容量m
 *  给水管，每过t1分钟状态改变，打开时注入m1
 *  排水管，每过t2分钟状态改变，打开时排走m2
 *  问经过t分钟后还有多少水。
 *  输入，m，t，m1，t1，m2，t2
 *  输出t分钟后的水量

#include<iostream>
 #include<string.h>
 #include<algorithm>
 #include<vector>
 using namespace std;
 
 
 int main(){
 	int T; cin >> T;
 	while (T--){
 		int m, t, m1, t1, m2, t2;
 		cin >> m >> t >> m1 >> t1 >> m2 >> t2;
 		bool if_in = true, if_out = true;
 		int in_time_left = t1, out_time_left = t2; int
 
 			speed = 0;
 		int water_left = 0;
 		while (t>in_time_left || t>out_time_left){
 			//input time > out time 
 			if (in_time_left > out_time_left){
 				//water situation
 				speed = 0;
 				if (if_in)speed += m1;
 				if (if_out)speed -= m2;
 				water_left +=
 
 					speed*out_time_left;
 				water_left = (water_left < 0) ? 0
 
 					: water_left;
 				water_left = (water_left > m) ? m
 
 					: water_left;
 
 				// statue situation
 				in_time_left -= out_time_left;
 				t -= out_time_left;
 				out_time_left = t2;
 				if (if_out)
 					if_out = false;
 				else
 					if_out = true;
 				continue;
 			}
 
 			if (in_time_left < out_time_left){
 				//water situation
 				speed = 0;
 				if (if_in)speed += m1;
 				if (if_out)speed -= m2;
 				water_left += speed*in_time_left;
 				water_left = (water_left < 0) ? 0
 
 					: water_left;
 				water_left = (water_left > m) ? m
 
 					: water_left;
 
 				// statue situation
 				out_time_left -= in_time_left;
 				t -= in_time_left;
 				in_time_left = t1;
 				if (if_in)
 					if_in = false;
 				else
 					if_in = true;
 				continue;
 			}
 
 			if (in_time_left == out_time_left){
 				//water situation
 				speed = 0;
 				if (if_in)speed += m1;
 				if (if_out)speed -= m2;
 				water_left += speed*in_time_left;
 				water_left = (water_left < 0) ? 0
 
 					: water_left;
 				water_left = (water_left > m) ? m
 
 					: water_left;
 
 				// statue situation
 				t -= in_time_left;
 				in_time_left = t1;
 				out_time_left = t2;
 				if (if_in)
 					if_in = false;
 				else
 					if_in = true;
 				if (if_out)
 					if_out = false;
 				else
 					if_out = true;
 				continue;
 			}
 		}
 
 		//last t min (t<=t1 && t<=t2)
 		speed = 0;
 		if (if_in)speed += m1;
 		if (if_out)speed -= m2;
 		water_left += speed*t;
 		water_left = (water_left < 0) ? 0 : water_left;
 		water_left = (water_left > m) ? m : water_left;
 		cout << water_left << endl;
 
 	}
 
 	//int end; cin >> end;
 	return 0;
 }

[Link 1]: https://baike.baidu.com/item/%E8%BF%90%E7%AD%B9%E5%AD%A6/1559
[Link 2]: https://baike.baidu.com/item/%E7%BE%8E%E5%9B%BD
[c_]: https://blog.csdn.net/weixin_36474809/article/details/97000362
[c_ O_n_ _ manacher_]: https://blog.csdn.net/weixin_36474809/article/details/100044593
[c_O_n_1_]: https://blog.csdn.net/weixin_36474809/article/details/100170310
[https_www.nowcoder.com_profile_368591124_test_25288703_377286_summary]: https://www.nowcoder.com/profile/368591124/test/25288703/377286#summary
[https_www.nowcoder.com_question_next_pid_17091533_qid_501354_tid_25319553]: https://www.nowcoder.com/question/next?pid=17091533&qid=501354&tid=25319553
[https_www.nowcoder.com_questionTerminal_7f24eb7266ce4b0792ce8721d6259800]: https://www.nowcoder.com/questionTerminal/7f24eb7266ce4b0792ce8721d6259800
[https_www.cnblogs.com_wuyepeng_p_9672154.html]: https://www.cnblogs.com/wuyepeng/p/9672154.html
[20190728134222128.png]: /images/20211126/43ef39977af04a9ab9030e7ee04e1773.png
[https_www.nowcoder.com_questionTerminal_f0605c09c4ab4b019bbfd6ef79130478_answerType_1_f_discussion]: https://www.nowcoder.com/questionTerminal/f0605c09c4ab4b019bbfd6ef79130478?answerType=1&f=discussion
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70]: /images/20211126/78870574c4db4f7da209f18489725033.png
[https_www.nowcoder.com_questionTerminal_8fb1e165abcb4b709d5a2f0ba759d0a6]: https://www.nowcoder.com/questionTerminal/8fb1e165abcb4b709d5a2f0ba759d0a6
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70 1]: /images/20211126/57443cf700524e49b7e1111e4c529955.png
[https_www.nowcoder.com_practice_6e5207314b5241fb83f2329e89fdecc8_tpId_13_tqId_11219_tPage_4_rp_4_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]: https://www.nowcoder.com/practice/6e5207314b5241fb83f2329e89fdecc8?tpId=13&tqId=11219&tPage=4&rp=4&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking