167. I-country.
time limit per test: 0.75 sec.
memory limit per test: 65536 KB
memory limit per test: 65536 KB
input: standard
output: standard
output: standard
According to top-secret A-country plans, I-country is divided into
N*M equal squares, each square contains some oil resources. They want to
occupy all the territory of I-country, but the UN (United Nations) will
allow them to occupy only K squares. Of course, A-country want to get
control over as many oil as possible, but, they will have to guard all
their territory. So, they need their territory to be easy-controlled,
i.e. from any square to any it must be possible to get moving only along
two directions (selected from the next list: left, right, up, down; for
different squares pairs of directions may differ).
You are to write a program, which determinies, what squares will be occupyed by A-country. If there are several solutions, you may output any.
You are to write a program, which determinies, what squares will be occupyed by A-country. If there are several solutions, you may output any.
Input
On the first line of input there are 3 integer numbers N,M,K
(1<=N,M<=15, 0<=K<=N*M). Next N lines contains M integers
each, which are the number of oil resource on that square. Each of this
numbers lies in range of 0 to 1000.
Output
On the first line of output, write string "Oil : X", where integer
number X --- the maximal number of oil which can be controlled by
A-country. Next you should output K pairs of numbers --- coordinates of
the squares which will be occupied by A-country. The first coordinate is
number of row (top to bottom, starting from 1), second is number of
column (left to right, starting from 1).
Sample test(s)
Input
2 3 4
10 20 30
40 2 3
10 20 30
40 2 3
Output
Oil : 100
1 1
1 2
1 3
2 1
1 1
1 2
1 3
2 1
好题！
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int n,m,k,ans,a1,a2,a3,a4,a5,cnt; 7 int sum[20][20],f[20][230][20][20][2][2],a[20][230][20][20][2][2]; 8 struct data{ 9 int h,z; 10 }dt[230]; 11 //f[row][i][l][r][x][y] x/y为0表示增，为1表示减 12 void add(int ro,int ii,int ll,int rr,int xx,int yy){ 13 if(ro==n) return; 14 for(int i=(!xx?1:ll);i<=rr;i++) 15 for(int j=max(i,ll);j<=(!yy?rr:m);j++){ 16 int t1,t2; 17 if(i==ll) t1=xx; 18 else t1=(i<ll?0:1); 19 if(j==rr) t2=yy; 20 else t2=(j<rr?0:1); 21 if(f[ro+1][ii+j-i+1][i][j][t1][t2]<f[ro][ii][ll][rr][xx][yy]+sum[ro+1][j]-sum[ro+1][i-1]){ 22 f[ro+1][ii+j-i+1][i][j][t1][t2]=f[ro][ii][ll][rr][xx][yy]+sum[ro+1][j]-sum[ro+1][i-1]; 23 a[ro+1][ii+j-i+1][i][j][t1][t2]=(ll<<12)+(rr<<8)+(xx<<4)+(yy); 24 } 25 } 26 } 27 void print(int ro,int ll,int rr,int xx,int yy,int kk){ 28 if(!ro||!kk) return; 29 for(int i=ll;i<=rr;i++) dt[++cnt].h=ro,dt[cnt].z=i; 30 print(ro-1,(a[ro][kk][ll][rr][xx][yy]>>12)%16,(a[ro][kk][ll][rr][xx][yy]>>8)%16,(a[ro][kk][ll][rr][xx][yy]>>4)%16,a[ro][kk][ll][rr][xx][yy]%16,kk-rr+ll-1); 31 } 32 bool cmp(const data&aa,const data&bb){ 33 if(aa.h!=bb.h) return aa.h<bb.h; 34 if(aa.z!=bb.z) return aa.z<bb.z; 35 } 36 int main(){ 37 scanf("%d%d%d",&n,&m,&k); 38 for(int i=1;i<=n;i++) 39 for(int j=1;j<=m;j++) scanf("%d",&sum[i][j]),sum[i][j]+=sum[i][j-1]; 40 memset(f,-1,sizeof(f)); 41 ans=-1; 42 for(int row=1;row<=n;row++) 43 for(int l=1;l<=m;l++) 44 for(int r=1;r<=m;r++) 45 for(int x=0;x<=1;x++) 46 for(int y=0;y<=1;y++){ 47 f[row][r-l+1][l][r][x][y]=sum[row][r]-sum[row][l-1]; 48 for(int i=r-l+1;i<=k;i++) 49 if(f[row][i][l][r][x][y]>0){ 50 add(row,i,l,r,x,y); 51 if(i==k&&f[row][i][l][r][x][y]>ans){ 52 ans=f[row][i][l][r][x][y]; 53 a1=row; 54 a2=l; 55 a3=r; 56 a4=x; 57 a5=y; 58 } 59 } 60 } 61 printf("Oil : %d ",ans); 62 print(a1,a2,a3,a4,a5,k); 63 sort(dt+1,dt+cnt+1,cmp); 64 for(int i=1;i<=cnt;i++) printf("%d %d ",dt[i].h,dt[i].z); 65 return 0; 66 }