ZOJ Monthly, June 2012 [7月9日暑假集训]

比赛地址：

http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=9231#overview

F .Choir III [最大子矩阵]

ZOJ地址：

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3616

　　因为不能选值为负的格子，所以将所有值为负预处理为 - INF。这样问题就变成：求一个矩阵的元素和最大的子矩阵，且满足至少b个boy，至少g个girl的问题。枚举行r和k，O(100*100)的复杂度，将r到k行的矩阵压缩成一个向量。再枚举右端点i，O(2000)的复杂度。维护当前值sum，num，len（以第i列结束的向量的最大值，向量包含的女生数，向量的长度），不断更新maxv。

F . Choir III

 1 //zzy2012.7.9AC
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<string>
 6 #include<cmath>
 7 #include<iostream>
 8 #include<algorithm>
 9 #include<map>
10 #include<vector>
11 #include<queue>
12 #define sf scanf
13 #define pf printf
14 #define pfn printf("\n");
15 #define ll long long
16 #define INF 0x7fffffff
17 
18 using namespace std;
19 
20 typedef struct{
21     long long v,s;
22 }node;
23 
24 long long n,m,b,g,v[100][2000],s[100][2000],maxv;
25 node a[2000];
26 
27 void D(){
28     long long len,sum,num,sp;
29     for(long long r=0; r<n; r++){
30         for(long long i=0; i<m; i++){
31             a[i].v=0;
32             a[i].s=0;
33         }
34         for(long long k=r; k<n; k++){
35             for(long long i=0; i<m; i++){
36                 a[i].v+=v[k][i];
37                 a[i].s+=s[k][i];
38             }
39             sum=0;
40             num=0;
41             len=0;
42             sp=k-r+1;
43             for(long long i=0; i<m; i++){
44                 if(sum>=0){
45                     sum+=a[i].v;
46                     num+=a[i].s;
47                     len++;
48                 }
49                 else{
50                     sum=a[i].v;
51                     num=a[i].s;
52                     len=1;
53                 }
54                 if(sum>=0){
55                     if(num>=g && sp*len-num>=b){
56                         if(sum>maxv)
57                             maxv=sum;
58                     }
59                 }
60             }
61         }
62     }
63 }
64 
65 int main()
66 {
67     while(sf("%lld %lld %lld %lld",&n,&m,&b,&g)!=EOF){
68         for(long long i=0; i<n; i++)
69             for(long long j=0; j<m; j++){
70                 sf("%lld %lld",&v[i][j],&s[i][j]);
71                 if(v[i][j]<0)
72                     v[i][j]=-INF;
73                 s[i][j]--;
74             }
75         maxv=-1LL;
76         D();
77         if(maxv==-1LL)
78             pf("No solution!\n");
79         else
80             pf("%lld\n",maxv);
81     }
82     return 0;
83 }

J .Escape Time II [BFS]

ZOJ地址：

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3620

　　房间数很少，边数可能比较多，所以先预处理下边。两个房间之间只记录花费时间最少的边。从前点开始BFS就行。需要注意的是状态压缩。要保存的状态：当前在哪个房间rid，去过了那些房间ar[10]，stid值是ar数组状态的二进制压缩。

J . Escape Time II

  1 //zzy2012.7.9AC
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cstdlib>
  5 #include<string>
  6 #include<cmath>
  7 #include<iostream>
  8 #include<algorithm>
  9 #include<map>
 10 #include<vector>
 11 //#include<queue>
 12 #define sf scanf
 13 #define pf printf
 14 #define pfn printf("\n");
 15 #define ll long long
 16 #define INF 0x7fffffff
 17 
 18 using namespace std;
 19 
 20 typedef struct{
 21     int rid,stid,v,t,ar[10];
 22 }node;
 23 
 24 int n,m,t,s,e,jew[10],way[10][10],front,rear,maxnum,p2[10],st[10][1024][2];//t , v
 25 node queue[1000000];
 26 
 27 void BFS(){
 28     node nd,nd2;
 29     front=rear=0;
 30     nd.rid=s;
 31     nd.v=jew[s];
 32     nd.stid=p2[s];
 33     nd.t=0;
 34     for(int i=0 ;i<n; i++) nd.ar[i]=0;
 35     nd.ar[s]=1;
 36     st[nd.rid][nd.stid][0]=0;
 37     queue[front++]=nd;
 38     while(front>rear){
 39         nd=queue[rear++];
 40         if(nd.t>t) continue;
 41         if(nd.rid==e)
 42             if(nd.v>maxnum) maxnum=nd.v;
 43         for(int i=0; i<n; i++){
 44             if(i==nd.rid) continue;
 45             nd2=nd;
 46             if(way[nd2.rid][i]==-1) continue;
 47             if(nd2.ar[i]==1){
 48                 nd2.t+=way[nd2.rid][i];
 49                 if(nd2.t>t) continue;
 50                 nd2.rid=i;
 51                 if(nd2.t<st[nd2.rid][nd2.stid][0]){
 52                     st[nd2.rid][nd2.stid][0]=nd2.t;
 53                     if(nd2.v>st[nd2.rid][nd2.stid][1])
 54                         st[nd2.rid][nd2.stid][1]=nd2.v;
 55                     queue[front++]=nd2;
 56                 }
 57                 else if(nd2.v>st[nd2.rid][nd2.stid][1]){
 58                     st[nd2.rid][nd2.stid][1]=nd2.v;
 59                     queue[front++]=nd2;
 60                 }
 61             }
 62             else if(nd2.t+way[nd2.rid][i]<=t){
 63                 nd2.ar[i]=1;
 64                 nd2.stid+=p2[i];
 65                 nd2.t+=way[nd2.rid][i];
 66                 nd2.v+=jew[i];
 67                 nd2.rid=i;
 68                 if(st[nd2.rid][nd2.stid][0]>nd2.t){
 69                     st[nd2.rid][nd2.stid][0]=nd2.t;
 70                     if(st[nd2.rid][nd2.stid][1]<nd2.v)
 71                         st[nd2.rid][nd2.stid][1]=nd2.v;
 72                     queue[front++]=nd2;
 73                 }
 74                 else if(st[nd2.rid][nd2.stid][1]<nd2.v){
 75                     st[nd2.rid][nd2.stid][1]=nd2.v;
 76                     queue[front++]=nd2;
 77                 }
 78             }
 79         }
 80     }
 81 }
 82 
 83 int main()
 84 {
 85     int a,b,c;
 86     p2[0]=1;
 87     for(int i=1; i<10; i++) p2[i]=p2[i-1]*2;
 88     //freopen("in.txt","r",stdin);
 89     while(sf("%d %d %d",&n,&m,&t)!=EOF){
 90         sf("%d %d",&s,&e);
 91         for(int i=0; i<n; i++)
 92             sf("%d",jew+i);
 93         for(int i=0; i<n; i++) for(int j=0; j<n; j++) way[i][j]=-1;
 94         for(int i=0; i<m; i++){
 95             sf("%d %d %d",&a,&b,&c);
 96             if(way[a][b]==-1 || way[a][b]>c){
 97                 way[a][b]=c;
 98                 way[b][a]=c;
 99             }
100         }
101         maxnum=0;
102         for(int i=0; i<n; i++) for(int j=0; j<1024; j++) {st[i][j][0]=INF; st[i][j][1]=0;}
103         BFS();
104         pf("%d\n",maxnum);
105     }
106     return 0;
107 }