hdu 2686 Matrix 듀얼 스레드 dp

왼쪽 상단에서 오른쪽 하단으로 가다가 왼쪽 상단으로 돌아가는 경로의 최대 권한치를 구한다. 돌아가는 과정이 있기 때문에 한 번에 가면 dp는 쓰기가 쉽지 않다. 여기서 경로를 왼쪽 상단에서 오른쪽 하각이 교차하지 않는 두 경로로 본다. dp[t][r][p][p][q][q]에 첫 번째 길이 (t,r)점과 두 번째 길이 (p,q)점까지 가는 최대 권한값이 저장되어 있어 방정식 dp[t][r][p][p][q][q][q][qqq](qqq==qqs=dfs=dfs=dfs=dfs(t,r)t-1, t-1, t-1, t-1, mqr, t-1, t-1, mr, mqr1(t-1, t-1, t-1, t-1, t-1, mrqq, q-1),dfs(t,r-1,p-1,q), dfs(t,r-1,p,q-1)+map[t][r]+map[p][q], 매번 dp 두 경로가 각각 한 걸음 앞으로 나아간다. 이렇게 가면 중복되지 않도록 (중점, 여기서부터 누락됨) 마지막으로 상태를 계산하기 전에 두 길을 같은 지점으로 가는 경우 dp[i][j][i][j]부성0,vis[j][j][j][j][j]][j]]를 계산하지 않고 같은 지점에 이르지 않는다.동일한 지점에 이르는 경우도 정확한 상황의 값에 영향을 주지 않는다.4차원의 수조를 3차원으로 바꿀 수도 있다. dp[k][i][j]는 모두 k보를 갔다. 첫 번째 길은 오른쪽으로 i보를 갔고 두 번째 길은 j보를 갔다. 그리고 걷는 걸음수에 따라 층층이 계산했다.
Matrix
Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 3   Accepted Submission(s) : 2
Problem Description
Yifenfei very like play a number game in the n*n Matrix. A positive integer number is put in each area of the Matrix.
Every time yifenfei should to do is that choose a detour which frome the top left point to the bottom right point and than back to the top left point with the maximal values of sum integers that area of Matrix yifenfei choose. But from the top to the bottom can only choose right and down, from the bottom to the top can only choose left and up. And yifenfei can not pass the same area of the Matrix except the start and end. 
 
Input
The input contains multiple test cases.
Each case first line given the integer n (2Than n lines,each line include n positive integers.(<100)
 
Output
For each test case output the maximal values yifenfei can get.
 
Sample Input

   
   
   
   

    
    
    
    2
10 3
5 10
3
10 3 3
2 5 3
6 7 10
5
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9

   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    28
46
80

   
   
   
   

 
Author
yifenfei
 
Source
ZJFC 2009-3 Programming Contest
 

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define s 30
int dp[s][s][s][s];
int vis[s][s][s][s];
int n;
int map[s][s];
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 dfs(int t,int r,int p,int q)
{
	int i,j,k,l;
	if(t<0||t>=n||r<0||r>=n||p<0||p>=n||q<0||q>=n)
		return 0;
	if(vis[t][r][p][q]==1)
		return dp[t][r][p][q];
	vis[t][r][p][q]=1;
	dp[t][r][p][q]=max(dfs(t-1,r,p-1,q),dfs(t-1,r,p,q-1),dfs(t,r-1,p-1,q),dfs(t,r-1,p,q-1))+map[t][r]+map[p][q];
	vis[t][r][p][q]=1;
	return dp[t][r][p][q];  
}

int main()
{
	int i,j,k,l;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				scanf("%d",&map[i][j]);
		memset(dp,0,sizeof(dp));
		memset(vis,0,sizeof(vis));
		dp[0][0][0][0]=0;
		vis[0][0][0][0]=1;
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				dp[i][j][i][j]=0;
				vis[i][j][i][j]=1;
			}
		}
		printf("%d
",dfs(n-1,n-2,n-2,n-1)+map[0][0]+map[n-1][n-1]);
	}
	return 0;
}