P7301 [USACO21JAN] Spaced Out S题目描述Farmer John 想要拍摄一张他的奶牛吃草的照片挂在墙上。草地可以用一个NNN行NNN列正方形方格所组成的方阵表示想象一个N×NN \times NN×N的棋盘其中2≤N≤10002 \leq N \leq 10002≤N≤1000。在 Farmer John 最近拍摄的照片中他的奶牛们太过集中于草地上的某个区域。这一次他想要确保他的奶牛们分散在整个草地上。于是他坚持如下的规则没有两头奶牛可以位于同一个方格。所有2×22 \times 22×2的子矩阵共有(N−1)×(N−1)(N-1) \times (N-1)(N−1)×(N−1)个必须包含恰好 2 头奶牛。例如这一放置方式是合法的CCC ... CCC而这一放置方式是不合法的因为右下的2×22 \times 22×2正方形区域仅包含 1 头奶牛C.C .C. C..没有其他限制。你可以假设 Farmer John 有无限多的奶牛根据以往的经验这种假设似乎是正确的……。Farmer John 更希望某些方格中包含奶牛。具体地说他相信如果方格(i,j)(i, j)(i,j)中放有一头奶牛照片的美丽度会增加aija_{ij}aij​0≤aij≤10000 \leq a_{ij} \leq 10000≤aij​≤1000单位。求合法的奶牛放置方式的最大总美丽度。输入格式输入的第一行包含NNN。以下NNN行每行包含NNN个整数。从上到下第iii行的第jjj个整数为aija_{ij}aij​的值。输出格式输出一个整数为得到的照片的最大美丽度。输入输出样例 #1输入 #14 3 3 1 1 1 1 3 1 3 3 1 1 1 1 3 3输出 #122说明/提示在这个样例中最大美丽度可以在如下放置方式时达到CC.. ..CC CC.. ..CC这种放置方式的美丽度为33313333223 3 3 1 3 3 3 3 223331333322。测试点性质测试点 2-4 满足N≤4N \le 4N≤4。测试点 5-10 满足N≤10N\le 10N≤10。测试点 11-20 满足N≤1000N \le 1000N≤1000。供题Hankai ZhangDanny MittalC实现#includebits/stdc.husingnamespacestd;constintN1010,M10010,INF0x3f3f3f3f;inlineintMax(intx,inty){returnxy?x:y;}inlineintMin(intx,inty){returnxy?x:y;}inlinevoidSwap(intx,inty){x^y^x^y;}intn,ans1,ans2,a[N][N];intline_sum(intj,inttype){intres[2]{0,0};for(inti1;in;i)res[i1]a[i][j];returnres[type];}introw_sum(inti,inttype){intres[2]{0,0};for(intj1;jn;j)res[j1]a[i][j];returnres[type];}intmain(){scanf(%d,n);for(inti1;in;i)for(intj1;jn;j)scanf(%d,a[i][j]);for(intk1;kn;k){if(line_sum(k,0)line_sum(k,1))ans1line_sum(k,0);elseans1line_sum(k,1);}for(intk1;kn;k){if(row_sum(k,0)row_sum(k,1))ans2row_sum(k,0);elseans2row_sum(k,1);}printf(%d\n,Max(ans1,ans2));return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容