HDU 2686 Matrix(マルチスレッドDP)
8167 ワード
Matrix
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1005 Accepted Submission(s): 558
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 (2 Than 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
Recommend
yifenfei
マルチプロセスDP、昨日初めて聞きました...
問題は,(1,1)から(n,n)への経路を2つ探し,重み値と最大でノードが重ならないようにすることである.
2つのプロセスを同時に進行させ、ステップKを1つ挙げ、x 1=x 2||y 1=y 2のときにスキップし、状態遷移方程式を得る.
dp(k, x1, y1, x2, y2) = max(dp(k-1, x1-1, y1, x2-1, y2), dp(k-1, x1-1, y1, x2, y2-1), dp(k-1, x1, y1-1, x2-1, y2), dp(k-1, x1, y1-1,x2, y2-1))
+ data(x1, y1) + data(x2, y2) ;
右または下しか歩けないため、座標はx+y=kを満たす.これにより、次元数を3次元に下げることができます.方程式:
dp(k, x1, x2) = max(dp(k-1, x1, x2), dp(k-1, x1-1, x2), dp(k-1, x1, x2-1), dp(k-1, x1-1, x2-1)) + data(x1, k-x1) + data(x2, k-x2) ;
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1005 Accepted Submission(s): 558
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 (2
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
Recommend
yifenfei
マルチプロセスDP、昨日初めて聞きました...
問題は,(1,1)から(n,n)への経路を2つ探し,重み値と最大でノードが重ならないようにすることである.
2つのプロセスを同時に進行させ、ステップKを1つ挙げ、x 1=x 2||y 1=y 2のときにスキップし、状態遷移方程式を得る.
dp(k, x1, y1, x2, y2) = max(dp(k-1, x1-1, y1, x2-1, y2), dp(k-1, x1-1, y1, x2, y2-1), dp(k-1, x1, y1-1, x2-1, y2), dp(k-1, x1, y1-1,x2, y2-1))
+ data(x1, y1) + data(x2, y2) ;
右または下しか歩けないため、座標はx+y=kを満たす.これにより、次元数を3次元に下げることができます.方程式:
dp(k, x1, x2) = max(dp(k-1, x1, x2), dp(k-1, x1-1, x2), dp(k-1, x1, x2-1), dp(k-1, x1-1, x2-1)) + data(x1, k-x1) + data(x2, k-x2) ;
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5
6 using namespace std;
7
8 int data[40][40],dp[80][40][40];
9
10 int Max(int a,int b,int c,int d){
11 return max(a,max(b,max(c,d)));
12 }
13
14 int main(){
15
16 //freopen("input.txt","r",stdin);
17
18 int n;
19 while(~scanf("%d",&n)){
20 int i,j,k;
21 for(i=0;i<n;i++)
22 for(j=0;j<n;j++)
23 scanf("%d",&data[i][j]);
24 memset(dp,0,sizeof(dp));
25 for(k=1;k<2*n-2;k++)
26 for(i=0;i<n;i++)
27 for(j=0;j<n;j++){
28 if(i==j)
29 continue;
30 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]);
31 dp[k][i][j]+=data[i][k-i]+data[j][k-j];
32 }
33 int ans=max(dp[k-1][n-1][n-2],dp[k-1][n-2][n-1])+data[0][0]+data[n-1][n-1];
34 printf("%d
",ans);
35 }
36 return 0;
37 }