Practice notes of Blue Bridge Cup algorithm (11): introduction to dynamic planning

11. Introduction to dynamic planning

A. One dimensional recurrence

1. Wrong arrangement

Staggered problem + recurrence problem

Some gentleman wrote n letters, there are n envelopes, if all the letters are packed in the wrong envelope, how many kinds of situations will there be?

#include<iostream>
using namespace std;

const int N=1e3+9;
long long f[N];

int main(){
	
	int n;
	cin>>n;
	//Method 1: array storage 
	f[1]=0,f[2]=1;
	for(int i=3;i<=n;i++){
		f[i]=(f[i-1]+f[i-2])*(i-1);
	}
	cout<<f[n]<<endl;
	
	//Method 2: spatial optimization  
	long long a=0,b=1,c=1;
	for(int i=3;i<=n;i++){
		c=(a+b)*(i-1);
		a=b;
		b=c;
	} 
	if(n!=1){a
		cout<<c<<endl; 
	}else{
		cou<<0<<endl;
	}
} 

2. Fibonacci series

/*Fibonacci series*/
#include<iostream>
using namespace std;

const int N=1e3;
long long f[N];

int main(){
	int n;
	cin>>n;
	//Method 1: use an array to store intermediate variables, which takes up a little more space 
	f[0]=f[1]=1;
	for(int i=2;i<=n;i++){
		f[i]=f[i-1]+f[i-2];
	}
	cout<<f[n]<<endl;
	
	//Method 2: continuous update, small space, unable to store intermediate variables
	long long a=1,b=1,c=1;
	for(int i=2;i<=n;i++){
		c=a+b;//i
		a=b;//i-2
		b=c;//i-1
	} 
	cout<<c<<endl;
	 
} 

B. Two dimensional recurrence

1. Yanghui triangle


#include<iostream>
using namespace std;
int n;
int a[10][10]= {0};

int main() {

	cin>>n;
	a[0][0]=1;
	for(int i=1; i<n; i++) {
		a[i][0]=1;
		for(int j=1; j<n; j++) {
			a[i][j]=a[i-1][j-1]+a[i-1][j];
		}
	}

	for(int i=0; i<n; i++) {
		for(int j=0; j<n; j++) {
			cout<<a[i][j]<<" ";
		}
		cout<<endl;
	}
	
	int m;
	cin>>m;
	cout<<a[n-1][m-1]<<endl;

	return 0;
}
/*
5
1 0 0 0 0
1 1 0 0 0
1 2 1 0 0
1 3 3 1 0
1 4 6 4 1
3
6
*/

2. crossing the river


	f[0][0]=1;
	for(int i=0; i<=n; i++) {
		for(int j=0; j<=m; j++) {
			if(i!=0) {
				f[i][j]=f[i][j]+f[i-1][j];
			}
			if(j!=0) {
				f[i][j]=f[i][j]+f[i][j-1];
			}
		}
	}
	//f[n][m] is the number of paths from (0,0) to (n,m)

	int cx,cy;
	int x[8]={1,1,2,2,-1,-1,-2,-2};//Lateral displacement 
	int y[8]={2,-2,1,-1,2,-2,1,-1};//Longitudinal displacement 
	int d[30][30];//Used to record whether it is a horse control point 
	for(int i=0;i<30;i++){//Convert d array to 0 
		for(int j=0;j<30;j++){
			d[i][j]=0;
		}
	}
	d[cx][xy]=1;//1 is the control point of the horse 
	for(int i=0;i<8;i++){
		int tx=cx+x[i];//Calculate coordinates of horse control points 
		int ty=cy+y[i];
		if(tx>=0 && tx<=n && ty>=0 && ty<=n){
			d[tx][ty]=1;//Record as horse control point 
		}
	}
#include<iostream>
using namespace std;
int dir[8][2]= {{1,2},{1,-2},{2,1},{2,-1},{-1,2},{-1,-2},{-2,1},{-2,-1}};
bool  d[30][30];
long long dp[30][30];
int main() {
	int n,m,cx,cy;// n. M chessboard size CX, position of XY horse
	cin>>n>>m>>cx>>cy;
	d[cx][cy]=true;
	for(int i=0; i<8; i++) {
		int tx=cx+dir[i][0];
		int ty=cy+dir[i][1];
		if(tx>=0 && tx<=n && ty>=0 && ty<=n) {
			d[tx][ty]=true;//Record as horse control point
		}
	}

	dp[0][0]=1;//dp[n][m] is the number of paths from (0,0) to (n,m)
	for(int i=0; i<=n; i++) {
		for(int j=0; j<=m; j++) {
			if(d[i][j]==false) {
				if(i) {
					dp[i][j]+=dp[i-1][j];
				}
				if(j) {
					dp[i][j]+=dp[i][j-1];
				}
			}
		}
	}

	cout<<dp[n][m]<<endl;
	return 0;
}
/*
Sample input:
5 5 2 4
 Sample output:
14 
*/

C. Introduction to dynamic planning / DP

1. Shortest path

/*Enter a map to find the shortest path from the top left corner to the bottom right corner, and only move to the right / down direction*/
#include<iostream>
#include<algorithm>
using namespace std;
int a[110][110];
int dp[110][110];
int main(){
	int n;
	cin>>n;
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	
	dp[1][1]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==1 && j==1){
				continue;
			}else if(i==1){
				dp[i][j]=dp[i][j-1]+a[i][j];
			}else if(j==1){
				dp[i][j]=dp[i-1][j]+a[i][j];
			}else{
				dp[i][j]=min(dp[i-1][j],dp[i][j-1])+a[i][j];
			}
		}
	}
	
	cout<<dp[n][n]<<endl;
	
	return 0;
}
/*
Sample input: 
3
0 3 4
6 2 5
5 4 3
 Sample output: 
12
*/

2. pick up fruit

#include<iostream>
#include<algorithm>
using namespace std;
int n;
int a[105][105]={0};
int dp[105][105]={0};

int main() {

	cin>>n;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=i; j++) {
			cin>>a[i][j];
		}
	}
	int ans=0;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=i; j++) {
			dp[i][j]=a[i][j]+max(dp[i-1][j],dp[i-1][j-1]);
			if(i==n){
				ans=max(dp[i][j],ans);
			}
		}
	}

	cout<<ans<<endl;
	cout<<"--output dp array--"<<endl;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=i; j++) {
			cout<<dp[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

/*
Sample input: 
4
3
1 2
6 2 3
3 5 4 1

Sample output: 
15
--Output dp array--
3
4 5
10 7 8
13 15 12 9 

*/

3. Suan tou Jun go home / 3D

/*Suan tou Jun goes home */
/*Suppose Suan tou Jun exists in three-dimensional space, and he wants to go home from (0,0,0) (n,n,n), every step she takes
 All of them will consume the physical strength of the current coordinate a[i][j][k]. Ask him how much physical strength he will consume to go home*/
#include<iostream>
#include<algorithm> 
using namespace std;
// Equation of state: 
// f[i][j][k] =  f[i][j][k] + min ( f[i-1][j][k] + f[i][j-1][k] + f[i][j][k-1] )

int f[105][105][105];
int inf=10000;
int main(){
	
	int x,y,z;
	cin>>x>>y>>z;
	for(int i=0;i<=x;i++){
		for(int j=0;j<=y;j++){
			for(int k=0;k<=z;k++){
				cin>>f[i][j][k];
			}
		}
	}
	
	for(int i=0;i<=x;i++){
		for(int j=0;j<=y;j++){
			for(int k=0;k<=z;k++){
				int mi=inf;
				if(i!=0){
					mi=min(mi,f[i-1][j][k]);
				}
				if(j!=0){
					mi=min(mi,f[i][j-1][k]);
				}
				if(k!=0){
					mi=min(mi,f[i][j][k-1]);
				}
				if(mi!=inf){
					f[i][j][k]+=mi;
				}
			}
		}
	}
	
	cout<<f[x][y][z]<<endl;
	return 0;
} 

/*
Sample input:
2 2 2 //Width of each one-dimensional coordinate (actually 3) 
1 2 3 // One dimensional coordinates 
4 5 6
7 8 9
1 2 3 // Two-dimensional 
4 5 6
7 8 9
1 2 3 // three-dimensional 
4 5 6
7 8 9
 Sample output: 
23
*/

4. climb stairs

#include<iostream>
using namespace std;
int n;
int mod=1e5+7;
int dp[1005];
int main(){
	cin>>n;
	dp[1]=1,dp[2]=2;
	for(int i=3;i<=n;i++){
		dp[i]=(dp[i-1]+dp[i-2])%mod;
	}
	cout<<dp[n]<<endl;
	
	return 0;
}
#include<iostream>
using namespace std;

const int mod=1e5+7;
int dp[1005];

int main(){
	
	int n;
	cin>>n;
	dp[0]=1;
	for(int i=1;i<=n;i++){
		dp[i]=0;
		for(int j=i-1;j>=0;j=j-2){
			dp[i]=dp[i]+dp[j];
			dp[i]=dp[i]%mod;
		}
	}
	cout<<dp[n]<<endl;
	return 0;
} 

/*
Input: 4
 Output: 3
*/

5. Passing game

/*Passing game: there are n players in A circle, passing from A to m times,
There are several ways to pass the ball back to A (different receiving order is regarded as different methods)*/
#include<iostream>
#include<cstring>
using namespace std;

int f[35][35];
int main(){
	int n,m; 
	cin>>n>>m;
	memset(f,0,sizeof(f));
	f[0][1]=1; // f [how many times has it been transmitted] = number of methods 
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			if(j==1){
				f[i][j]=f[i-1][2]+f[i-1][n];
			}else if(j==n){
				f[i][j]=f[i-1][1]+f[i-1][n-1];
			}else{
				f[i][j]=f[i-1][j-1]+f[i-1][j+1];
			}
		}
	}
	cout<<f[m][1]<<endl;
	cout<<endl;
}
/*
cin:  
3 3
cout:  
2 
*/

6. One dimensional xiaoxiaole

One dimensional xiaoxiaole is a game that is not a single game. There are several rows, each bead has a value (possibly negative).
The rule of the game is that you can choose several pairs of adjacent beads, let them disappear at the same time. The disappearance of each pair of beads will make the total score plus the score of two beads multiplication. Note that each bead can only be removed once, and after the bead is removed, it will occupy a place.

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=10005;
int dp[maxn][2];//1 represents the combination with the front, 0 represents no combination with the front
int w[maxn]; 
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i];
	}
	dp[1][0]=0;
	for(int i=2;i<=n;i++){
		dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
		dp[i][1]=dp[i-1][0]+w[i]*w[i-1]; 
	}
	cout<<max(dp[n][0],dp[n][1])<<endl;
	return 0;
} 
/*
cin:
8
-9 -5 -4 -2 4 -5 -4 2
cout:
73
*/

7. Array grouping

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1010;
const int mod=1000;

int a[maxn];
int dp[maxn];
int pre[maxn][maxn];


int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		pre[i][i]=a[i];
		for(int j=i+1;j<=n;j++){
			pre[i][j]=pre[i][j-1]*a[j]%mod;
		}
	}
	dp[0]=0;
	dp[1]=a[1];
	for(int i=2;i<=n;i++){
		for(int j=0;j<i;j++){
			dp[i]=max(dp[i],dp[j]+pre[j+1][i]);
		}
	} 
	cout<<dp[n]<<endl;
	
	return 0;
}
/*
cin:
7
52 26 1 36 72 48 43
cout:
1596
*/

8. Wall painting

#include<iostream>
using namespace std;

int n;
int a[100]; 

int main() {

	cin>>n;	
	a[1]=3;//A wall 
	a[2]=6;
	a[3]=6;
	for(int i=4; i<=n; i++) {
		a[i]=a[i-1]+a[i-2]+a[i-2];
		//The color of the first wall is different from that of the i-1 wall. There are a[i-2] types of the i-wall 
		//The color of the first wall is the same as that of the i-1 wall. There are a[i-2] types of the i-wall 
	}
	cout<<a[n]<<endl;

	return 0;
}
/*
cin:
4
cout: 
18 
*/

9. crossing the river

On a dark night with high wind, there are n (n < = 50) children on one side of the bridge. Because the bridge is very narrow, no more than 2 people are allowed to pass through each time. They only have one flashlight, so the two people who cross the bridge each time need to bring the flashlight back. The crossing time of No. I child is T[i], and the total crossing time of two people is the longer of the two. What is the shortest time for all children to cross the bridge? Answer train of thought

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int n;
int a[1005];
int f[1005];//How many people used to use the time with the flashlight on the opposite side 

int main(){
	
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	
	sort(a,a+n);//Ascending order 
	f[0]=a[0];
	f[1]=a[1];
	
	for(int i=2;i<n;i++){
		f[i]=min(f[i-1]+a[0]+a[i],f[i-2]+a[0]+2*a[1]+a[i]); 
	}
	cout<<f[n-1]<<endl;
	return 0;
}
/*
cin:
4
1 5 6 7
cout:
20 
*/
Published 20 original articles, won praise 10, visited 1059
Private letter follow

Posted on Thu, 12 Mar 2020 19:50:59 -0700 by superdan_35