nyoj 61 (이중 스레드 dp)
2012 단어 dp
한 행렬에서 1, 1에서 m, n의 경로 두 개(하나는 1, 1에서 m, n은 m, n에서 1, 1)를 찾아내고 경로 위의 권한의 합이 가장 크다.
문제풀이 사고방식: 이 문제가 (1,1)->(n,m)에서, 다시 (n,m)->(1,1)에서라면 분명히 생각이 나지 않을 것이다.비교적 좋은 방법은 두 가지 경로가 있다고 보는 것이다(1,1)->(n,m). 이렇게 하면 상태 F[i][j][k][l]=max{F[i-1][j][k-1][l], F[i-1][j][k][k][l-1], F[i][j+1][k-1][l], F[i][j+1][k][k][l-1]+a[k].
의미: 쪽지 한 장이 i, j 다른 한 장이 k, l로 전달될 때 경로상의 권한의 최대 값.
여기서 한 가지 문제를 고려해야 한다. 두 길이 겹치는 곳이 있는지, 사실은 그렇지 않다. 왜냐하면 우리가 먼저 i, j, k, l를 제어하면 서로 같지 않다. 즉, 같은 점에 교차하지 않는다. 그 다음에 우리가 전달할 때 두 길이 함께 간다. 어느 길이 먼저 가지 않으면 두 길의 일치성을 확보할 수 있다.
자세히 관찰하면 이런 결론을 쉽게 얻을 수 있다. 쪽지가 전하는 가로 좌표 + 세로 좌표 = 걷는 걸음수;이 결론을 통과하면 매우 간단한 소위이다.
참조 블로그:http://blog.csdn.net/zy691357966/article/details/7795365
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 55;
int n,m;
int map[maxn][maxn],dp[maxn<<1][maxn][maxn];
int Max(int a,int b,int c,int d)
{
if(a >= b && a >= c && a >= d) return a;
if(b >= a && b >= c && b >= d) return b;
if(c >= a && c >= b && c >= d) return c;
if(d >= a && d >= b && d >= c) return d;
}
int main()
{
int t;
cin >> t;
while(t--)
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> map[i][j];
memset(dp,0,sizeof(dp));
for(int k = 1; k <= n + m - 2; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
{
if(i == n && j == n && k == n + m - 2)
dp[k][i][j] = Max(dp[k-1][i][j],dp[k-1][i-1][j],dp[k-1][i][j-1],dp[k-1][i-1][j-1]) + map[i][k+2-i] + map[j][k+2-j];
else if(i != j && k + 2 - i >= 1 && k + 2 - j >= 1)
dp[k][i][j] = Max(dp[k-1][i][j],dp[k-1][i-1][j],dp[k-1][i][j-1],dp[k-1][i-1][j-1]) + map[i][k+2-i] + map[j][k+2-j];
}
printf("%d
",dp[n+m-2][n][n]);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
