1032.机器人 |
Time Limit: 1000 MS Memory Limit: 65536 KB Total Submission(s): 34 Accepted Submission(s): 7 |
Description |
SYC喜欢宅在家里,但又不喜欢清理垃圾,有一天实在看不下去了,就把好友ZZK和LG叫来帮忙。没想到他俩更懒,把各自的机器人带过来了,当然,大家都不愿意为这两台机器人设计程序,所以请你来帮忙。
为了运算的简单,我们将SYC的屋子看做N*M的矩阵,在矩阵的每一个坐标上都可能有不同数量的垃圾。已知开始时这两个机器人都放在矩阵的左上角,两个机器人每次都只能向右或向下走一步,而且不能向回走,也不能走另一个机器人走过的坐标。现在请你帮忙,计算这两个机器人都走到右下角时打扫垃圾的最大数量。 |
Input |
第一行有两个整数N和M,分别表示SYC家占地N行M列。1<=N,M<=50。
接下来有N行,每行有M个数据,表示N*M的矩阵,每行各个数字使用空格分隔。矩阵第i行j列的数字表示该处垃圾的个数。 |
Output |
输出打扫垃圾的最大数量
|
Sample Input |
3 3 0 9 9 6 1 8 2 3 0 |
Sample Output |
37 |
据说这是双线程DP,也叫二路DP,不明觉厉。
#include<iostream> #include<cstring> #include<stdio.h> using namespace std; int dp[130][65][65]={0}; int a[65][65]; int maxn(int a,int b){ if(a>b) return a; else return b; } int minn(int a,int b){ if(a<b) return a; else return b; } int maxx(int a,int b,int c,int d){ return maxn(d,maxn(c,maxn(b,a))); } int main(){ int n,m; int i,j,k; int s1,s2; cin>>n>>m; for(i=1;i<=n;i++) for(j=1;j<=m;j++) cin>>a[i][j]; for(i=1;i<=m+n-2;i++){ s1=minn(i+1,n); //边界控制值得好啊 s2=maxn(i-m+1,1); for(j=s2;j<=s1;j++) for(k=s2;k<=s1;k++){ if(j==k) continue; int kk=maxx(dp[i-1][j-1][k-1],dp[i-1][j-1][k],dp[i-1][j][k-1],dp[i-1][j][k]); dp[i][j][k]=kk+a[j][i-j+1]+a[k][i-k+1]; } } cout<<maxn(dp[m+n-2][n][n-1],dp[m+n-2][n-1][n]); return 0; }