Algorithm training - > dynamic programming

Title Description

Obuchi and Xiaoxuan are good friends and classmates. They always have endless topics together. In a quality development activity, the students in the class arranged to make a matrix of M rows and N columns, while Obuchi and Xiaoxuan were arranged at both ends of the diagonal of the matrix, so they couldn't talk directly. Fortunately, they can communicate by passing notes. The note should be passed to each other through many students. Obuchi sits in the upper left corner of the matrix with coordinates (1,1), and Xiaoxuan sits in the lower right corner of the matrix with coordinates (m,n). The note from Xiaoyuan to Xiaoxuan can only be passed down or right, and the note from Xiaoxuan to Xiaoyuan can only be passed up or left.

During the activity, Obuchi hopes to pass a note to Xiaoxuan and hope Xiaoxuan will reply to him. Every student in the class can help them pass, but will only help them once. That is to say, if this person helps when Xiaoxuan hands Xiaoxuan the note, he will not help when Xiaoxuan hands it to Xiaoyuan. vice versa.

Another thing to note is that each student in the class is willing to help with varying degrees of favor (Note: the degree of kindness of Obuchi and Xiaoxuan is not defined, and it is expressed as 0 when entering). It can be expressed by a natural number of 0-100. The larger the number, the better. Obuchi and Xiaoxuan hope to find students with a high degree of kindness to help pass the note, that is, to find two transmission paths back and forth, so that the kindness of the students on these two paths is only the same as the maximum. Now, please help Obuchi and Xiaoxuan find these two paths.

Enter Description:

Enter two integers m and N separated by spaces in the first row, indicating that there are m rows and N columns in the class (1 < = m, n < = 50).
The next m row is a matrix of m*n. the integer in row i and column j of the matrix represents the kindness of the students sitting in row i and column j. The N integers in each line are separated by spaces.

Output Description:

The output consists of one line, including an integer, which represents the maximum value of the sum of the kindness of the students involved in passing the note on the two roads back and forth.

Example 1

input

3 3
0 3 9
2 8 5
5 7 0

output

34

remarks:

30% of the data meet: 1 < = m, n < = 10
 100% of the data meet: 1 < = m, n < = 50

[[code implementation]
/*
ID:shijieyywd
PROG:Vijos-1493
LANG:c++
*/
#include <stdio.h>
#include <string.h>
 
int arr[52][52];
/*
* re[x1][y1][x2][y2]express
* The maximum favorability of students whose coordinates are (x1, y1) and (x2, y2)
*/
int re[52][52][52][52];
 
int max(int a, int b, int c, int d) {
	if (a < b) a = b;
	if (a < c) a = c;
	if (a < d) a = d;
	return a;
}
 
int main ( void ) {
	int m, n;
	int x1, y1, x2, y2;
	scanf("%d %d", &m, &n);
	
	for (x1 = 1; x1 <= m; x1++) {
		for (y1 = 1; y1 <= n; y1++) {
			scanf("%d", &arr[x1][y1]);
		}
	}
	for (x1 = 1; x1 <= m; x1++) {
		for (y1 = 1; y1 <= n; y1++) {
			for (x2 = 1; x2 <= m; x2++) {
				if (x1 + y1 - x2 > 0) {
					y2 = x1 + y1 - x2;
				} else continue;
				re[x1][y1][x2][y2] = max(re[x1-1][y1][x2-1][y2],
									re[x1][y1-1][x2-1][y2],
									re[x1][y1-1][x2][y2-1],
									re[x1-1][y1][x2][y2-1])
									+ arr[x1][y1] + arr[x2][y2];
				if (x1 == x2 && y1 == y2) {
					re[x1][y1][x2][y2] -= arr[x1][y1];
				}
			}
		}
	}
	printf("%d", re[m][n][m][n]);
 
	return 0;
}

 

Title Description

Xiaoming's florist is newly opened. In order to attract customers, he wants to put a row of flowers in m pots at the door of the florist. By investigating customers' preferences, Xiao Ming listed the customers' favorite N kinds of flowers, with labels from 1 to n. In order to display more kinds of flowers at the door, it is stipulated that the first kind of flowers can not exceed the ai basin. When arranging flowers, the same kind of flowers should be placed together, and different kinds of flowers should be arranged in order from small to large.

Try programming to calculate how many different flower arrangement schemes there are.

Enter Description:

The first line is separated by n and a space in the m iddle.

The second line has n integers, separated by a space between each two integers, representing a1, a2,... an in turn.

Output Description:

The output has only one line and an integer, indicating how many schemes there are. Note: since the number of schemes may be many, please output the result of the modulo of 1000007.

Example 1

input

2 4
3 2

output

2

explain

There are two flower arrangement schemes, namely (1, 1, 1, 2), (1, 1, 2, 2). 1 and 2 in brackets represent two kinds of flowers. For example, the first scheme is to place the first flower in the first three positions and the second flower in the fourth position.

remarks:

For 20% data, there are 0 < n ≤ 8, 0 < m ≤ 8, 0 ≤ ai ≤ 8;

For 50% data, there are 0 < n ≤ 20, 0 < m ≤ 20, 0 ≤ ai ≤ 20;

For 100% data, there are 0 < n ≤ 100, 0 < m ≤ 100, 0 ≤ ai ≤ 100.

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int Mod=1000007;
int n,m,a[105],f[105][105];
  int main(){
     //freopen("1077.in","r",stdin);
      //freopen("1077.out","w",stdout);
     scanf("%d%d",&n,&m);
     f[0][0]=1;
    for(register int i=1;i<=n;i++)
         scanf("%d",&a[i]);
     for(register int i=1;i<=n;i++)
         for(register int j=m;j>=0;j--)
            for(register int k=0;k<=a[i]&&j-k>=0;k++)
                f[i][j]+=f[i-1][j-k]%Mod;
     printf("%d\n",f[n][m]%Mod);
     return 0;
 }