P1006 传纸条
输入输出样例
输入 #1 复制
3 3
0 3 9
2 8 5
5 7 0
输出 #1 复制
34
说明/提示
【限制】
对于 30% 的数据，1≤m,n≤10； 对于 100% 的数据满1≤m,n≤50
NOIP 2008提高组第三题
思路如下
这一题应该是可以看成由两种解法，但是也可以看成一种解法，题解三四可以看成是题解一 ，优化掉一维的结果。
题解传送门
题解一(四维dp)
#include <iostream>
#define maxn 55
using namespace std;
int f[maxn][maxn][maxn][maxn],a[maxn][maxn];
int n,m;
int max_ele(int a,int b,int c,int d){if (b>a)a = b;if (c>a)a = c;if (d>a)a = d;return a;
}
int main(){cin >> n >> m;for (int i=1;i<=n;i++)for (int j=1;j<=m;j++) cin >> a[i][j];for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)for (int k=1;k<=n;k++)for (int l=j+1;l<=m;l++) f[i][j][k][l]=max_ele(f[i][j-1][k-1][l],f[i-1][j][k][l-1],f[i][j-1][k][l-1],f[i-1][j][k-1][l])+a[i][j]+a[k][l];cout << f[n][m-1][n-1][m] << endl;return 0;
}
题解二（三维dp）
#include <iostream>
#include <cstring>
#include <cstdio>
#define maxn 55
using namespace std;
int f[2 * maxn][maxn][maxn];
int a[maxn][maxn];
int n,m;int max_ele(int a,int b,int c,int d){if (b>a)a = b;if (c>a)a = c;if (d>a)a = d;return a;
}int main(){cin >> n >> m;for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)cin >> a[i][j];for (int k=1;k<=n+m-1;k++)for (int i=1;i<=n;i++)for (int j=1;j<=n;j++){if (k-i+1<1 || k-j+1<1) //这里是判断纵坐标的合法性，如果纵坐标不合法那就跳过去continue;f[k][i][j] = max_ele(f[k-1][i][j],f[k-1][i-1][j-1],f[k-1][i][j-1],f[k-1][i-1][j]) + a[i][k-i+1] + a[j][k-j+1];if (i==j) //判断重合路径f[k][i][j]-=a[i][k-i+1];}cout << f[n+m-1][n][n] << endl;return 0;
}
题解三
#include<iostream>
#include<string.h>
using namespace std;
const int Len = 100;
long long int dp[Len*2][Len][Len];
long long int map[Len][Len];int main()
{freopen("T.txt","r",stdin);int m,n;scanf("%d %d", &m, &n);for(int i = 1; i <= m; i ++)for(int j = 1; j <= n; j ++)scanf("%lld", &map[i][j]);//初始化dpmemset(dp , -1 , sizeof(dp));dp[2][1][1] = 0; //原点好心值为 0//核心dpfor(int i = 3; i < m + n; i ++)for(int j = 1; j < n; j ++)for(int k = j + 1; k <= n; k ++){cout<< i - k<<endl;long long int tem = dp[i][j][k];if(dp[i - 1][j][k] > tem) tem = dp[i - 1][j][k];if(dp[i - 1][j - 1][k] > tem) tem = dp[i - 1][j - 1][k];if(dp[i - 1][j][k - 1] > tem) tem = dp[i - 1][j][k - 1];if(dp[i - 1][j - 1][k - 1] > tem) tem = dp[i - 1][j - 1][k - 1];if(tem == -1) //如果tem的值为-1 那么说明这个点是不存在的continue;dp[i][j][k] = tem + map[i - j][j] + map[i - k][k];}printf("%lld\n",dp[m + n - 1][n - 1][n]);return 0;
}