请问我的程序为何自测Ac,却过不了数据#2?

还请大神指导

测试数据 #0: Accepted, time = 0 ms, mem = 2532 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 2660 KiB, score = 10
测试数据 #2: RuntimeError, time = 78 ms, mem = 4556 KiB, score = 0
测试数据 #3: Accepted, time = 0 ms, mem = 2536 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 2528 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 2536 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 2540 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 2536 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 2560 KiB, score = 10
测试数据 #9: Accepted, time = 93 ms, mem = 2612 KiB, score = 10
RuntimeError, time = 231 ms, mem = 4556 KiB, score = 90

#include<stdio.h>
#include<stdlib.h>
int high[505][505]={0},vis[505][505]={0},l[505]={0},r[505]={0};
int dx[5]={-1,0,0,1};
int dy[5]={0,-1,1,0};
int n,m,t;
void dfs(int x,int y)
{
int i,tx,ty;
vis[x][y]=t;
for(i=0;i<4;i++)
{
tx=x+dx[i];
ty=y+dy[i];
if( tx>0&&tx<=n && ty>0&&ty<=m && high[x][y]>high[tx][ty] && vis[tx][ty]!=t ) dfs(tx,ty);
}
}
int main()
{
//freopen("flow3.in","r",stdin);
//freopen("flow.out","w",stdout);
int i,j,k,flag=0,w,ans=0;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&high[i][j]);
for(i=1;i<=m;i++)
{
t=i;
dfs(1,i);//求i号蓄水场能到达的 第n行城市线段
for(j=1;j<=m;j++)
if(vis[n][j]==t) break;
if(j>m) continue;//i号蓄水场无贡献
l[i]=j;//左端点
for(j=m;j>0;j--)
if(vis[n][j]==t) break;
r[i]=j;//右端点
}
for(i=1;i<=m;i++)//有城市未被管理,无解
if(vis[n][i]==0)
{
flag=1;
ans++;
}
if(flag==1) printf("0\n%d",ans);
else//此时可以证明:每个蓄水场管理区间l[i]~r[i]连续
{
w=0;//第n行的城市看成线段,当前已覆盖长度为1~w
while(1)
{
for(i=1;i<=m;i++)//截去无效部分
if(l[i]<w+1) l[i]=w+1;
k=0;
for(i=1;i<=m;i++)//寻找恰好"顶头"且最长的线段
if(l[i]==w+1&&k<r[i]) k=r[i];
ans++;
w=k;
if(w==m) break;
}
printf("1\n%d",ans);
}
//system("pause");
return 0;
}

麻烦大家了。

2 条评论

  • @ 2015-06-22 14:02:24

    还是不行,不过谢谢啦!

  • @ 2015-06-14 14:15:50

    dfs的时候会爆栈空间!!
    你可以开O2试一下

  • 1

信息

ID
1777
难度
7
分类
动态规划 点击显示
标签
递交数
2974
已通过
565
通过率
19%
被复制
10
上传者