[NOIP2008]传纸条（含空间压缩优化）_综合

分析

这道题和NOIP2000的方格取数如出一辙（我写的超详细题解在此），都是给定矩阵，要求从左上角走到最下角（只可向右或向左走）找两条路径，使两条路径上数字的总和最大。但这题有几个变化：

路径不可相交。
矩阵形态不一样：原题是方阵，这题是任意矩阵。但这个变化没有什么影响。
数据范围有所扩大：原题是9以内，这题是50。但如果用动规做，O(n³）的时间复杂度依旧不会超时。

解法依然是动规，两条路线同时走，状态是[y1][x1][y2][x2]表示两条路线分别走到(x1,y1)和(x2,y2)……阶段、状态转移方程也都一样，省略100～200字…….为了确保路径不可相交，不妨设路线1始终在路线2的左侧，可以加上x1<x2这个限制条件来确保。

时间复杂度O(n³），空间复杂度O(n⁴）。

代码

注意

状态转移时，要判断上一状态是否在边界内、是否合法。
如果对最后一轮也加了限制条件，需把最后状态从[m][n][m][n]改成[m][n-1][m-1][n]（倒数第二轮的状态），路线1的终点和路线2的终点只有这一种可能，一个在终点左边一格，一个在终点上边一格。
当m或n为1时，无法找到两个不相交路径，需输出0。

#include <stdio.h>
#include <string.h>int max(int a,int b) {
    return a>b?a:b;}/* dp[y1][x1][y2][x2] (x1<x2) = max{a[y1][x1] + a[y2][x2] + max{dp[y1-1][x1][y2-1][x2], dp[y1][x1-1][y2][x2-1], dp[y1-1][x1][y2][x2-1], dp[y1][x1-1][y2-1][x2]}} */const int dir[2][2]={
    {
    1,0},{
    0,1}};int main()
{
    // load dataint m,n;while (2==scanf("%d%d",&m,&n)){
    static int a[51][51];static int dp[51][51][51][51];int x,y,num;memset(a,0,sizeof(a));memset(dp,-1,sizeof(dp));for (int y=1;y<=m;y++)for (int x=1;x<=n;x++)scanf("%d",&a[y][x]);// solve (dynamic planning)dp[1][1][1][1]=a[1][1];// round z (z=1...m+n-1)for (int round=1;round<m+n;round++){
    //printf("round %d\n", round);if (round==1) continue;// (x, y) | x+y == round+1for (int x1=1;x1<=n;x1++){
    int y1=round+1-x1;if (y1>=1 && y1<=m){
    for (int x2=x1+1;x2<=n;x2++){
    int y2=round+1-x2;if (y2>=1 && y2<=m){
    //printf("(y1,x1),(y2,x2): (%d,%d) (%d,%d)\n",y1,x1,y2,x2);for (int z1=0;z1<2;z1++){
    for (int z2=0;z2<2;z2++){
    if (y1-dir[z1][0]>=1 && x1-dir[z1][1]>=1 && y2-dir[z2][0]>=1 && x2-dir[z2][1]>=1){
    int tmp = dp[y1-dir[z1][0]][x1-dir[z1][1]][y2-dir[z2][0]][x2-dir[z2][1]];if (tmp == -1) continue; // unreachable statedp[y1][x1][y2][x2] = max(dp[y1][x1][y2][x2], tmp + a[y1][x1] + (x1!=x2?a[y2][x2]:0));}}}//printf("dp[%d][%d][%d][%d]=%d\n",y1,x1,y2,x2,dp[y1][x1][y2][x2]);}}}}}if (m>1 && n>1)printf("%d\n",dp[m][n-1][m-1][n]);elseputs("0");}return 0;
}

优化

这题的说有点弱，因为动规解法的时间复杂度不高，只有O（n³），实际上n到200也可在一秒内出解，唯一的问题是空间占用比较大，需要O（n⁴）。

一级优化：考虑到每个状态中都有x1+y1=x2+y2，因而这四维中存在冗余维，可减少一维变成[round][x1][x2]，空间复杂度降为O（n³）。

二级优化：考虑到每个状态[round][x1][x2]的计算只需要[round-1]的状态，因此只保留这一轮和上一轮的状态值就够了。可用滚动数组实现，空间复杂度降为2×n²。

三级优化：考虑到每个状态[round][x1][x2]的计算只依赖于[round-1][x1-1][x2]、[round-1][x1][x2-1]、[round-1][x1-1][x2-1]、[round-1][x1][x2]这四个状态。如果我们去掉第一维round，并对后两维x1、x2采用逆序迭代策略，先算完一轮，不要清空，然后在算第二轮时会发现每个状态依赖的四个上一轮状态值还都在（当前轮）的数组里，比如算到[x1][x2]时，上一轮的[x1-1][x2]仍在f[x1-1][x2]里，还没有被这一轮覆盖，相当于可以（从当前轮的状态数组）取到上一轮的状态。每一轮、每一个状态计算时都是如此。从而将空间复杂度降到n²。

二级优化、三级优化都可以顺利通过增强版的大教室中传纸条题目。

三级优化代码

改动是将四维dp数组改成了二维的minidp数组，颠倒了i、j迭代顺序。
注意，计算minidp[i][j]时需要用到minidp[i][j]（上一轮的），用完上一轮的值后再存放本轮的minidp[i][j]的值。

#include <stdio.h>
#include <assert.h>
#include <string.h>int max(int a,int b) {
    return a>b?a:b;}/* dp[y1][x1][y2][x2] (x1<x2) = max{a[y1][x1] + a[y2][x2] + max{dp[y1-1][x1][y2-1][x2], dp[y1][x1-1][y2][x2-1], dp[y1-1][x1][y2][x2-1], dp[y1][x1-1][y2-1][x2]} (if (y1,x1) != (y2, x2)).a[y1][x1] + max{...same with above}} */const int dir[2][2]={
    {
    1,0},{
    0,1}};int main()
{
    // load dataint m,n;while (2==scanf("%d%d",&m,&n)){
    static int a[51][51];//static int dp[51][51][51][51];static int minidp[51][51];int x,y,num;memset(a,0,sizeof(a));//memset(dp,-1,sizeof(dp));memset(minidp,-1,sizeof(minidp));for (int y=1;y<=m;y++)for (int x=1;x<=n;x++)scanf("%d",&a[y][x]);// solve (dynamic planning)//dp[1][1][1][1]=a[1][1];minidp[1][1]=a[1][1];// round z (z=1...m+n-1)for (int round=1;round<m+n;round++){
    //printf("round %d\n", round);if (round==1 || round==m+n-1) continue;// (x, y) | x+y == round+1for (int x1=n;x1>=1;x1--){
    int y1=round+1-x1;if (y1>=1 && y1<=m){
    for (int x2=n;x2>x1;x2--){
    int y2=round+1-x2;if (y2>=1 && y2<=m){
    int result=-1;//printf("(y1,x1),(y2,x2): (%d,%d) (%d,%d)\n",y1,x1,y2,x2);for (int z1=0;z1<2;z1++){
    for (int z2=0;z2<2;z2++){
    if (y1-dir[z1][0]>=1 && x1-dir[z1][1]>=1 && y2-dir[z2][0]>=1 && x2-dir[z2][1]>=1){
    int tmp;//tmp = dp[y1-dir[z1][0]][x1-dir[z1][1]][y2-dir[z2][0]][x2-dir[z2][1]];//if (tmp == -1) continue; // unreachable state//dp[y1][x1][y2][x2] = max(dp[y1][x1][y2][x2], tmp + a[y1][x1] + (x1!=x2?a[y2][x2]:0));tmp = minidp[x1-dir[z1][1]][x2-dir[z2][1]];result = max(result, tmp + a[y1][x1] + a[y2][x2]);//assert(result == dp[y1][x1][y2][x2]);}}}minidp[x1][x2]=result;//printf("dp[%d][%d][%d][%d]=%d\n",y1,x1,y2,x2,dp[y1][x1][y2][x2]);}}}}}if (m>1 && n>1)printf("%d\n",/*dp[m][n-1][m-1][n],*/minidp[n-1][n]);elseputs("0");}return 0;
}