vijos1011&poj1088:记忆化搜索+DP【名正言顺的AC】

代码

http://poj.org/problem?id=1088
https://vijos.org/p/1011
今天终于名正言顺地A掉了这一题,为什么说是名正言顺呢,因为之前做的我是半抄别人代码的,而现在我在没有任何提示(包括之前的记忆,已经忘掉了= =)的情况下半小时AC了这题..而且时间刚刚好是昨年..那时我用了三天,不多说,上代码:)
旧版:


/*Source Code
2015-09-22 21:18:43
Problem: 1088 User: aclolicon
Memory: 972K Time: 16MS
Language: C++ Result: Accepted*/
Source Code
#include<cstring>
#include<cstdio>
//#include<iostream>
//#include<algorithm>
#define max(a,b) a>b?a:b
int r,c;
int h[1000][1000];
int f[1000][1000];
int bigs=-1;
int dfs(int x,int y){
if (f[x][y]>1) return f[x][y];

if(x>r || y>c || x<1 || y<1) {
return 0;
}
for (int i=-1;i<=1;i++)
for (int j=-1;j<=1;j++){ //if(i==j) continue;
if ((i==1&&j==0)||(i==-1&&j==0)||(i==0&&j==-1)||(i==0&&j==1))
{
if (h[x+i][y+j]>=h[x][y]) continue;

f[x][y]=max(f[x][y],(dfs(x+i,y+j))+1);
}else continue;
}
//std::cout<<x<<" " <<y<<" "<<f[x][y]<<std::endl;
bigs=max(bigs,f[x][y]);
return f[x][y];
}
int main(){
//freopen("c.txt","r",stdin);
scanf("%d%d",&r,&c);
for (int i=0;i<=r;i++)
for (int j=0;j<=c;j++){
f[i][j]=1;
h[i][j]=-1;
}
for (int i=1;i<=r;i++)
for (int j=1;j<=c;j++)
scanf("%d",&h[i][j]);

for (int i=1;i<=r;i++)
for (int j=1;j<=c;j++)
dfs(i,j);

/*for (int i=1;i<=r;i++)
{
printf("\n");
for (int j=1;j<=c;j++)
printf("%d ",f[i][j]);}*/
printf("%d",bigs);
return 0;
}

今晚的:


/*Source Code
2016-09-20 22:03:41
Problem: 1088 User: aclolicon
Memory: 1452K Time: 32MS
Language: G++ Result: Accepted
Source Code*/
#include<cstdio>
#include<iostream>
#define MAXN 555
#include<cstring>
#define absx(a) a<0?-a:a
using namespace std;
int n, m;
int g[MAXN][MAXN];
int dp[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dfs(int x, int y){
// cout << x << y << endl;
bool flag = 0;
if (dp[x][y] != -1) return dp[x][y];

int tmp = 0, maxi = 1;
for (int i = -1; i <= 1; i++)
for (int j = -1; j <= 1; j++){
if ((i != 0 && j != 0) || (i == 0 && j == 0)) continue;
if (x + i > n || x + i < 1 || y + j > m || y + j < 1) continue;
// cout << x + i << " " << y + j << endl;
if (g[x + i][y + j] < g[x][y]) tmp = dfs(x + i, y + j), flag = 1;
if (tmp > maxi) maxi = tmp;
}
if (!flag){
dp[x][y] = 1;
return 1;
}
dp[x][y] = maxi + 1;
vis[x][y] = 1;
return dp[x][y];
}

int main(){
memset(vis, 0, sizeof(vis));
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++){
scanf("%d", &g[i][j]);
dp[i][j] = -1;
}
/* for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cout << dp[i][j] << " ";
}
cout << endl;
}*/
int ans = -1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++){
int t = dfs(i, j);
if (t > ans) ans = t;
}
/*for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cout << dp[i][j] << " ";
}
cout << endl;
}*/

cout << ans << endl;
}


虽然用时稍长,但是今晚值得庆祝..

我还没有学会写个人说明!

发表评论

电子邮件地址不会被公开。 必填项已用*标注