首页 > 代码库 > HDU 2686 (双线程) Matrix
HDU 2686 (双线程) Matrix
这也是当初卡了很久的一道题
题意：从左上角的格子出发选一条路径到右上角然后再回到左上角，而且两条路径除了起点和终点不能有重合的点。问所经过的格子中的最大和是多少
状态设计：我们可以认为是从左上角出发了两条路径，然后同时到达右下角。容易看出，第k个阶段所有可能到达的格子构成一条斜线而且满足x1 + y1 = x2 + y2 = k + 1
dp[k][x1][x2]表示第k阶段两条路分别到达(x1, y1) (x2, y2)所能取得的最大值(y1 y2根据上面的等量关系来计算)，如果x1 = x2表示两条路径汇合于一点了
状态转移方程：
在求解第k阶段最优解时，首先枚举k-1阶段时的状态(x1‘, x2‘)，然后向四个方向延伸出(x1, x2)
dp[k][x1][x2] = max{dp[k-1][x1‘][x2‘] + num[x1][y1] | (x1=x2), dp[k-1][x1‘][x2‘] + num[x1][y1] + num[x2][y2] | (x1≠x2)}
在循环的过程中可能会出现从一个点延伸的下一个点的情况，即两条路径可能重合，不过不要紧，因为格子里面都是正数，所以得到的最优解一定是两条不重合的路径
优化：
因为两条路径具有任意性，所以不妨规定第一条路在第二条路的下方(或同一水平线)，时间从92MS优化到62MS
第k阶段状态的转移只依赖第k-1阶段的状态，可以用滚动数组(由于原来的空间本不大，所以代码中没有实现滚动数组)
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 int dp[70][35][35], num[35][35], n; 8 9 bool islegal(int x, int y)10 {11 return (x>=1 && x<=n && y>=1 && y<=n);12 }13 14 int main(void)15 {16 #ifdef LOCAL17 freopen("2686in.txt", "r", stdin);18 #endif19 20 int i, j, k, d1, d2, x1, x2, y1, y2;21 while(scanf("%d", &n) == 1)22 {23 memset(dp, 0, sizeof(dp));24 for(i = 1; i <= n; ++i)25 for(j = 1; j <= n; ++j)26 scanf("%d", &num[i][j]);27 28 dp[1][1][1] = num[1][1];29 for(k = 2; k <= 2*n-1; ++k)30 {31 for(i = 1; i <= k - 1; ++i)32 for(j = 1; j <= i; ++j)33 {//枚举两条路径在k-1步时的状态34 for(d1 = 0; d1 <= 1; ++d1)35 for(d2 = 0; d2 <= 1; ++d2)36 {//共四个延伸方向37 x1 = i + d1, y1 = k + 1 - x1;38 x2 = j + d2, y2 = k + 1 - x2;39 if(islegal(x1, y1) && islegal(x2, y2))40 {41 if(x1 == x2)42 dp[k][x1][x2] = max(dp[k][x1][x2], dp[k-1][i][j] + num[x1][y1]);43 else44 dp[k][x1][x2] = max(dp[k][x1][x2], dp[k-1][i][j] + num[x1][y1] + num[x2][y2]);45 }46 }47 }48 }49 printf("%d\n", dp[2*n-1][n][n]);50 }51 return 0;52 }
HDU 2686 (双线程) Matrix
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。