1, Informatics OJ: 1275: [example 9.19] maximum product
(1) Title Description
This year is the "2000 - world year of mathematics" determined by the International Mathematical Union, and coincides with the 90th anniversary of the birth of Mr. Hua Luogeng, a famous mathematician in China. In Jintan, Jiangsu, Mr. Hua Luogeng's hometown, a new mathematical intelligence contest was organized, and one of your good friends XZ was lucky to participate. During the activity, the host gave all the participants a question:
There is a number string with a length of N. players are required to use K multiplication signs to divide it into K+1 parts, and find a division method to maximize the product of K+1 parts.
At the same time, in order to help the contestants correctly understand the meaning of the question, the host also gave the following example:
There is a number string: 312. When N=3 and K=1, there are the following two methods:
1)3*12=36
2)31*2=62
At this time, the result that meets the requirements of the topic is: 31 * 2 = 62.
Now, please help your good friend XZ design a program to get the right answer.
[input]
The first row has two natural numbers N, K (6 ≤ N ≤ 10, 1 ≤ K ≤ 6)
The second line is a numeric string of length N.
[output]
Output the maximum product obtained (a natural number).
[input example]
4 2 1231
[output example]
62
(2) Code implementation
Copy code to sticker board
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define N 500
using namespace std;
int maxx[N][N], num[N][N];
char number[N];
int n, k;
int main() {
scanf("%d%d", &n, &k);
getchar();
scanf("%s", number);
for(int i = 0; i < n; i++) {
num[i+1][i+1] = number[i] - '0';
}
for(int j = 2; j <= n; j++) {
for(int i = j-1; i >= 1; i--) {
num[i][j] = num[i][j-1] * 10 + num[j][j];
}
}
for(int i = 1; i <= n; i++) {
maxx[i][0] = num[1][i];
}
for(int l = 1; l <= k; l++) {
for(int i = l+1; i <= n; i++) {
for(int j = l; j <= i-1; j++) {
maxx[i][l] = max(maxx[i][l], maxx[j][l-1] * num[j+1][i]);
}
}
}
printf("%d\n", maxx[n][k]);
return 0;
}2, Informatics OJ:1274: [example 9.18] merge stones
(1) Title Description
[Title Description]
N piles of stones are placed in rows on a playground. Now we need to merge the stones into a pile in order. It is stipulated that only two adjacent piles of stones can be selected each time to combine into a new pile, and the number of new piles of stones shall be recorded as the score of the combination.
Calculate the minimum score of combining n piles of stones into one pile.
[input]
The first line is a positive integer N (2 ≤ n ≤ 100);
In the following N lines, each line is a positive integer, less than 10000, representing the number of stones in the ith rockfill (1 ≤ i ≤ N).
[output]
A positive integer, that is, the minimum score.
[input example]
7 13 7 8 16 21 4 18
[output example]
239
(2) Code implementation
Copy code to sticker board
#include<bits/stdc++.h>
using namespace std;
int n,m,a[1001],f[1001][1001];
int main(){
scanf("%d",&n);
memset(f,127,sizeof(f));
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
a[i]+=a[i-1];
f[i][i]=0;
}
for(int i=n;i>=1;i--){
for(int j=i+1;j<=n;j++){
for(int k=i;k<j;k++)
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+a[j]-a[i-1]);
}
}
cout<<f[1][n]<<endl;
return 0;
}3, Informatics OJ: 1280: [example 9.24] skiing
(1) Problem description
[Title Description]
Xiao Ming likes skiing, because skiing is really exciting, but in order to obtain speed, the sliding area must tilt downward. When Xiao Ming slides to the bottom of the slope, he has to go uphill again or wait for a helicopter to pick him up. Xiao Ming wants to know the longest landslide in an area. The length of landslide is calculated by the number of sliding points, and the area is given by a two-dimensional array. Each number of the array represents the height of the points. Here is an example:
1161514132172423123182522114192021105678912345161718196152425207142322218131211109
A person can slide from a certain point to one of the four adjacent points up and down, left and right. If and only if the height decreases, in the above example, a feasible landslide is 25-24-17-16-1 (from 25 to 1). Of course, 25-24... 2-1 is longer. In fact, this is the longest one.
[input]
The first input line represents the row number R and column number C (1 ≤ R, C ≤ 100) of the two-dimensional array of the region. The following is row R, and the number of C in each row represents the height.
[output]
The longest landslide length in the output area.
[input example]
5 5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
[output example]
25
(2) Code implementation
Copy code to sticker board
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll,int>P;
const ll INF=1e17+10;
const int N=105,mod=1e9+7;
int a[N][N];
int n,m;
int tmp;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int h[N][N];
int dfs(int x,int y){//Traversal starting from (x,y)
int mx=0;
if(h[x][y])return h[x][y];
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]<a[x][y]){
mx=max(mx,dfs(nx,ny));
}
}
return h[x][y]=mx+1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dfs(i,j);
}
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ans=max(ans,h[i][j]);
}
}
printf("%d\n",ans);
}