【DP】방격취수와 【DP】전쪽지

제목.

N*N이 있는 격자 그래프(N<=10, 우리는 그 중 일부 칸에 정수를 채우고 다른 칸에는 숫자 0을 넣는다. 아래 그림과 같다(예시 참조): [외사슬 그림 저장 실패(img-qDv9 Spoy-1562483002948)(http://10.156.17.250/JudgeOnline/image/1010.jpg)]
누군가가 그림의 왼쪽 상단의 A점에서 출발하면 아래로 걸어갈 수도 있고 오른쪽으로 걸어서 오른쪽 하단의 B점에 도달할 수도 있다.지나가는 길에 그는 네모난 칸의 수를 가져갈 수 있다(가져간 칸은 숫자 0으로 바뀔 것이다).이 사람은 A점에서 B점까지 모두 두 번 걸으며 이런 경로 두 개를 찾아내 얻은 수의 합이 가장 크다.

입력

입력한 첫 번째 동작은 정수 N(N*N을 나타내는 네모난 그림)이고 그 다음 줄마다 세 개의 정수가 있으며 앞의 두 개는 위치를 나타내고 세 번째 수는 그 위치에 놓인 수입니다.별도의 행 0은 입력이 끝났음을 나타냅니다.

출력

2개의 경로에서 얻은 최대 합계를 나타내는 정수만 출력할 수 있습니다.

샘플 가져오기

8 2 3 13 2 6 6 3 5 7 4 4 14 5 2 21 5 6 4 6　3 15 7　2 14 0　0 0

출력 예제

67

문제풀이의 방향

이 문제는'욕심 계산법'일 수도 있다.일부 상황에서 욕심 알고리즘도 가장 좋은 결과를 낼 수 있지만 전체적으로 말하자면'욕심 알고리즘'은 뚜렷한 결함이 있는 알고리즘이다.실제로 본 문제는 동태적인 기획으로 해결할 수 있지만 점차적으로 더 복잡해질 뿐이다. 앞에서 한 번만 걷는 상황을 고려하고 있다.한 사람이 어떤 칸(i, j)에 도달하는 상황을 고려하면 공식을 내놓을 수 있다. f[i] [j] [k] [k] [s] = m a x f [i] [j] [s] =max f[i] [j] [s] [i] [s] =max 첫 번째 max(f[i] [i] [1] [j] [k-1] [k-1] [s] [s] [s] [s] [s] [s] [j] [j] [j] [s] [j] [s] [s] [s] [s] [j] [s] [s] [s] [s] [s] [s] [s] [s] [s] [s] [s] [s] [s] [s] [s] [s] [[s] [s] [[max(f[i-3-1][j][k-31][s], f[i-3-1][j][k][s-31]) 두 번째 max(f[i][j-1][k-31][s] , f [ i ] [ j − 1 ] [ k ] [ s − 1 ] ) max(f[i][j-1][k-1][s],f[i][j-1][k][s-1]) max(f[i][j−1][k−1][s],f[i][j−1][k][s−1])

주의

i≠k 또는 j≠s

절차는 다음과 같다.

#include
#include
#include 
using namespace std;
int f[12][12][12][12],a[12][12],n,x,y,z;
int main() 
{
    scanf("%d",&n);
    scanf("%d%d%d",&x,&y,&z);
      while(x!=0&&y!=0&&z!=0)//           0         
      {
	    a[x][y]=z;// x,y   z，             
	    scanf("%d%d%d",&x,&y,&z);
      }
    for(int i=1;i<=n;i++)//     
        for(int j=1;j<=n;j++)//     
            for(int k=1;k<=n;k++)//     
                for(int s=1;s<=n;s++)//     
				{
                    f[i][j][k][s]=max(max(f[i-1][j][k-1][s],f[i-1][j][k][s-1]),max(f[i][j-1][k-1][s],f[i][j-1][k][s-1]))+a[i][j]+a[k][s];
                      if(i==k && s==j)//          ，     a[i][j]    
					    f[i][j][k][s]=f[i][j][k][s]-a[i][j];
				}
       printf("%d",f[n][n][n][n]);
        return 0;
}
 

제목.

소연과 소헌은 좋은 친구이자 같은 반 친구이다. 그들은 함께 있으면 늘 끝낼 수 없는 화제가 있다.한 차례의 소양 확대 활동에서 반 학생들은 m행 n열의 행렬을 만들었고 소연과 소헌은 행렬 대각선의 양쪽에 배치되어 직접 이야기를 나눌 수 없었다.다행히도 그들은 쪽지를 보내서 의사소통을 할 수 있었다.쪽지는 많은 학우들을 거쳐 상대방에게 전해져야 한다. 소연은 행렬의 왼쪽 상단, 좌표(1,1), 소헌은 행렬의 오른쪽 하단, 좌표(m,n)에 앉는다.소연에서 소헌으로 전해지는 쪽지는 아래로 또는 오른쪽으로만 전달되고, 소연에서 전해지는 쪽지는 위로 또는 왼쪽으로만 전달된다.행사 진행 중 샤오옌은 샤오쉬안에게 쪽지 한 장을 전달하고 샤오쉬안이 그에게 답장을 주기를 바란다.반의 모든 학우들이 전달을 도와줄 수 있지만 한 번만 도와줄 수 있다. 즉, 만약에 이 사람이 소연이에게 쪽지를 건네줄 때 도와주면 소연이에게 건네줄 때 도와주지 않는다는 것이다.반대로 해도 마찬가지다.또 하나 주의해야 할 것은 반 전체의 모든 학우들이 도와주고 싶은 호감도가 높고 낮다는 것이다. (주의: 소연과 소헌의 호의도는 정의가 없고 입력할 때 0으로 표시한다) 0-100의 자연수로 표시할 수 있다. 숫자가 클수록 호의를 나타낸다.소연과 소헌은 가능한 한 호의도가 높은 학우를 찾아서 쪽지를 전달하는 것을 도와주기를 바란다. 즉, 왕복 두 가지 전달 경로를 찾아서 이 두 가지 경로에서 학우들의 호의도가 가장 높을 뿐이다.지금, 소연과 소헌이 이런 두 가지 경로를 찾을 수 있도록 도와주세요.

입력

파일 메시지 입력.n의 첫 줄에는 두 개의 빈칸으로 구분된 정수 m와 n이 있는데 반에 m줄 n열이 있음을 나타낸다(1<=m, n<=50).다음 m행은 m*n의 행렬로 행렬에서 i행 j열의 정수는 i행 j열에 앉아 있는 학생들의 호의를 나타낸다.각 행의 정수 n을 공백으로 구분합니다.

출력

출력 파일 메시지.아웃은 모두 한 줄로 하나의 정수를 포함하여 두 길을 오가며 쪽지를 전달하는 학생들의 호의도와 최대치를 나타낸다.

샘플 가져오기

3 3 0 3 9 2 8 5 5 7 0

출력 예제

34

문제풀이의 방향

사실 격자 취수와 차이가 많지 않은데, 이것도 왜 함께 놓고 쳤는가

진짜 많이 차이 안 나요.

진짜 많이 차이 안 나요.

진짜 많이 차이 안 나요.

진짜 많이 차이 안 나요.

더 이상 말하지 않겠다

절차는 다음과 같다.

#include
#include
using namespace std;
int f[51][51][51][51],a[51][51],n,m;
int main() 
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
    {
    	for(int j=1;j<=n;j++)//              
    	{
    		 scanf("%d",&a[i][j]);
    	}
    }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=m;k++)
                for(int s=1;s<=n;s++){
                    f[i][j][k][s]=max(max(f[i-1][j][k-1][s],f[i-1][j][k][s-1]),max(f[i][j-1][k-1][s],f[i][j-1][k][s-1]))+a[i][j]+a[k][s];
                      if(i==k && s==j)
					    f[i][j][k][s]=f[i][j][k][s]-a[i][j];
					}
       printf("%d",f[m][n][m][n]);
        return 0;
}