当前位置:网站首页>Luogu p1006 pass note

Luogu p1006 pass note

2021-07-30 02:56:41 Birds eat crickets

Title Description

Xiaoyuan and Xiaoxuan are good friends and classmates , They have a lot to talk about together . In a quality development activity , The class arranged to make one m That's ok n Columns of the matrix , And Xiaoyuan and Xiaoxuan are arranged at both ends of the diagonal of the matrix , therefore , They can't talk directly . Fortunately, , They can communicate by passing notes . The note has to be passed to each other through many students , Xiaoyuan sits in the upper left corner of the matrix , coordinate (1,1), Xiaoxuan sits at the bottom right corner of the matrix , coordinate (m,n). The note from Xiaoyuan to Xiaoxuan can only be passed down or to the right , The note from Xiaoxuan to Xiaoyuan can only be passed up or left .

In progress , Xiaoyuan hopes to deliver a note to Xiaoxuan , At the same time, I hope Xiaoxuan will reply to him . Everyone in the class can pass it on for them , But only once , That is to say, if this person helps Xiaoxuan when Xiaoyuan hands him the note , Then when Xiaoxuan hands it to Xiaoyuan, he won't help again . vice versa .

One more thing to note , Everyone in the class is willing to help ( Be careful : There is no definition of the degree of kindness of Xiaoyuan and Xiaoxuan , Input time 0 Express ), You can use a 0-100 It's a natural number , The greater the number, the better . Xiaoyuan and Xiaoxuan hope to find students with high degree of kindness to help pass the notes , I.e. find two transfer paths back and forth , Make the best of the two paths . Now? , Please help Xiaoyuan and Xiaoxuan find such two paths .

I / O format

Input format :

 

Input file message.in There is the first line 2 Integers separated by spaces m and n, It means there are m That's ok n Column (1<=m,n<=50).

Next m Row is one. m*n Matrix , In matrix i That's ok j The integer representation of the column sits at i That's ok j The degree of kindness of the students . Per row n Integers separated by spaces .

 

Output format :

 

The output file message.out All in one line , Contains an integer , Represents the maximum value of the sum of the kindness degree of the students participating in the transfer of the notes on the two routes back and forth .

 

I/o sample

sample input #1:
3 3
0 3 9
2 8 5
5 7 0
sample output #1:
34

explain

【 Limit 】

30% Data of :1<=m,n<=10

100% Data of :1<=m,n<=50

NOIP 2008 Improve group 3

 

Section dp 

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

int f[51][51][51][51],n,a[51][51],m;
int main()
{
    scanf("%d%d",&n,&m);
    int i,j,k,l;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++) scanf("%d",&a[i][j]);
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            for (k=1;k<=n;k++)
                for (l=j+1;l<=m;l++) f[i][j][k][l]=max(max(f[i][j-1][k-1][l],f[i-1][j][k][l-1]),max(f[i][j-1][k][l-1],f[i-1][j][k-1][l]))+a[i][j]+a[k][l];
    printf("%d\n",f[n][m-1][n-1][m]);
    return 0;
}

 

We are all boating on the lake of destiny , The waves heaved and we couldn't escape the lonely voyage . But if we lose our way , The waves will guide us through the dawn of another day .
 
 
 
 

版权声明
本文为[Birds eat crickets]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/07/20210727154328982K.html