上午写了一次(http://zqynux.blog.163.com/blog/static/1674995972010101325737526/)，只有70分，剩下的我也知道为什么错了，所以我的思路是不行的，但是我就想不到另外的方法了，到群里问了下，别人把代码发给我看了,, 汗, 好简单, 纯DP, 没有任何杂念, 我原本以为要排序, 但NOIP的题目似乎涉及不到这么高深的算法, 矩阵+排序+搜索, 就觉得我是想复杂了, 他这个代码太简单了…
但是几乎是纯递归,我以为会爆掉(栈溢出), 结果用最最最大的可能用尽栈的数据测试, 结果没溢出, 后来测试发现,, 栈一般还是够用..
但是我犯了一个很严重的错误, 记忆DP竟然没有给它记忆,, 所以导致最后一个数据超时了,,代码如下:
int map[100][100];
int dis[100][100];
int r, c;
int check(int a,
int b)
{
if(a < 0 || a >= r
|| b < 0 || b >= c){
return 0;
}
return 1;
}
int max(int a,
int b)
{
return a > b ? a : b;
}
#define deal(i, j) do{\
if(check(i, j) && map[i][j] >
map[a][b]){\
t = max(srch(i, j),
t);\
}\
}while(0)
int srch(int a, int b)
{
int t = 0;
if(dis[a][b] != 0){
return dis[a][b];
}
deal(a +
1, b);
deal(a – 1, b);
deal(a, b + 1);
deal(a, b – 1);
/
Mistack 1:
真是….不好怎么评价自己了,, 记忆DP, 我竟然忘记记忆了..
/
dis[a][b]
= t + 1;
return dis[a][b];
}
int main(void)
{
int ans = 1;
int i, j,
t;
scanf("%d%d", &r,
&c);
for(i = 0; i < r; i++){
for(j = 0; j < c;
j++){
scanf("%d",
&map[i][j]);
}
}
for(i = 0; i < r;
i++){
for(j = 0; j < c; j++){
t = srch(i,
j);
if(ans <
t){
ans =
t;
}
}
}
printf("%d\n", ans);
return 0;
}