首页 > 代码库 > NOIP模拟题——集结蚂蚁
NOIP模拟题——集结蚂蚁
【题目描述】
雄心勃勃的企业家达伦·克劳斯发现了皮姆博士有关缩小原子间距离的公式并
研发出新一代微型“黄蜂战士”，皮姆博士担忧武器会引发不可挽回的后果，于是
找到斯科特并使他成为了新一代“蚁人”。正逢克劳斯与外商交易黄蜂战衣的那天，
斯科特受命前往摧毁黄蜂战衣并销毁数据，然而一个人的力量是渺小的，斯科特需
要走入一个巨大的蚁穴去召唤蚂蚁与他共同作战。
蚁穴是一个巨大复杂的地带，由n 行m 列组成，每个偶数行存在至少一个蚂蚁
聚集地，同一行的不同蚂蚁聚集地以一堵墙隔开，每个蚂蚁聚集地的大小为Si；
每个奇数行存在连接相邻偶数行中蚂蚁聚集地的路径，一个蚂蚁聚集地可能有多条
路径可以到达。
蚁人可从蚁穴的第一行任何一路口出发，由于时间紧迫，蚁人只能向下一行走，
在这种情况下，蚁人希望你能告诉他如何使经过的蚂蚁聚集地大小之和最大，从而
召唤最多的蚂蚁。
【输入】
第1 行包含两个用空格隔开的整数n，m，意义见描述。
第2 到n+1 行，每行m 个字符（无间隔）且仅存在0 和1：同一偶数行中连
续x 个0 组成一个大小为x 的蚂蚁聚集地，1 为墙体；奇数行中0 表示蚁人可以从
此处通过。
【输出】
对于每组数据输出一个整数，表示经过路径中最大聚集地之和（不包含聚集
地之间的路径）。若蚁人无法到达最后一行则请输出“-1”。
4
【输入样例】
10 10
1111101111
1100001011
1101111111
1100000101
1110110111
1000110001
1101111011
1101000011
1101011111
1101010001
【输出样例】
17
【样例解释】
【数据规模】
对于20%的数据，n≤20,m≤20
对于50%的数据，n≤20,m≤100
对于100%的数据，n≤5000,m≤2000，保证n 是一个偶数，路径的数量不多于1×106
在输入的时候存每一行连续0的个数，若其中有一个0上面也是0(即是可以走的)，便更新它的权值，到最后或碰到1时，看上一个可行点
是否可以更改权值。
后面直接就每一行每一行搜索了，由于存的是区间，每个区间只扫一次，所以最大时间复杂度O(mn)。
好像用建图SPFA做也可以。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 using namespace std; 5 const int maxn=5005; 6 const int maxm=2005; 7 int map[maxn][maxm];//1000w 8 int pos[maxn][maxm>>1];//500w(不连在一起的位置) 9 int f[maxn][maxm];//1000w 10 int w[maxn][maxm>>1];//500w 11 int n,m; 12 int main() 13 { 14 freopen("ant.in","r",stdin); 15 freopen("ant.out","w",stdout); 16 scanf("%d%d",&n,&m); 17 int t=0;int pre=1;bool pd=false; 18 for(int i=1;i<=n;i++) 19 { 20 t=0; 21 for(int j=1;j<=m;j++) 22 { 23 char c=getchar(); 24 while(c!=‘0‘&&c!=‘1‘)c=getchar(); 25 map[i][j]=c-‘0‘; 26 27 28 if(i==1)continue; 29 30 if(map[i][j]==0) 31 t++; 32 if(map[i][j]==1&&pd==false){t=0;continue;} 33 if(map[i][j]==1&&pos[i][pos[i][0]]+t>=j&&pd==true) 34 { 35 w[i][pos[i][0]]=t; 36 t=0;pd=false; 37 } 38 if(map[i][j]==0&&map[i-1][j]==0)//可以标记 39 { 40 pd=true; 41 if(pos[i][0]==0) 42 { 43 pos[i][++pos[i][0]]=j; 44 w[i][pos[i][0]]=t; 45 } 46 else if(pos[i][pos[i][0]]+t-1>=j) 47 { 48 pos[i][pos[i][0]]=j; 49 } 50 else 51 pos[i][++pos[i][0]]=j; 52 } 53 if(pd==true&&j==m&&map[i][j]==0) 54 { 55 w[i][pos[i][0]]=t; 56 } 57 } 58 } 59 for(int i=1;i<=m;i++) 60 f[1][i]=-1; 61 for(int i=2;i<=n;i++) 62 for(int j=1;j<=pos[i][0];j++) 63 { 64 if(i%2==0)//聚集地 65 { 66 if(i!=2) 67 { 68 int k=pos[i][j];int k2=pos[i][j]; 69 int v=w[i][j];int er=0; 70 while(map[i][k]==0) 71 { 72 if(k==0)break; 73 er=max(er,f[i-1][k]); 74 k--; 75 }k++; 76 while(map[i][k2]==0) 77 { 78 if(k2==m+1)break; 79 er=max(er,f[i-1][k]); 80 k2++; 81 }k2--; 82 if(er==0)continue; 83 else 84 { 85 for(int as=k;as<=k2;as++) 86 f[i][as]=er+v; 87 } 88 } 89 else 90 { 91 int k=pos[i][j];int k2=pos[i][j]; 92 int v=w[i][j]; 93 while(map[i][k]==0) 94 { 95 if(k==0)break; 96 k--; 97 }k++; 98 while(map[i][k2]==0) 99 {100 if(k2==m+1)break;101 k2++;102 }k2--;103 for(int as=k;as<=k2;as++)104 f[i][as]=v;105 }106 }107 else108 {109 int k=pos[i][j];int k2=pos[i][j];110 int v=f[i-1][pos[i][j]];111 while(map[i][k]==0)112 {113 if(k==0)break;114 v=max(f[i-1][k],v);115 k--;116 }k++;117 while(map[i][k2]==0)118 {119 if(k2==m+1)break;120 v=max(f[i-1][k2],v);121 k2++;122 }k2--;123 if(v==0)continue;124 else125 {126 for(int as=k;as<=k2;as++)127 f[i][as]=v;128 }129 } 130 }131 int ans=0;132 for(int i=1;i<=m;i++)133 if(f[n][i]>ans)ans=f[n][i];134 if(ans==0)135 printf("-1");136 else137 printf("%d",ans);138 return 0;139 }
NOIP模拟题——集结蚂蚁