打卡信奥刷题（3116）用C++实现信奥题 P7365 [CTSC2002] 颁奖典礼

P7365 [CTSC2002] 颁奖典礼题目背景IOI2002 的颁奖典礼将在 YONG-IN Hall 隆重举行。人们在经历了充满梦幻的世界杯之后变得更加富于情趣。为了使颁奖典礼更具魅力有人建议在 YONG-IN Hall 中搭建一个I\text{I}I字型的颁奖台以此代表信息学 Informatics。考虑到比赛的赞助商们可能要在 YONG-IN Hall 中摆设了许多展示台他们可能不愿意移动展示台的位置。你作为 IOI2002 的金牌得主自然地成为了他们求助的对象。题目描述YONG-IN Hall 是一个矩形的网格区域。每个赞助商的展示台都占据了若干个单位网格。I\text{I}I型颁奖台将正向搭建且平行于 YONG-IN Hall 的边缘。I\text{I}I型颁奖台是由三个矩形相接叠成的其中上方和下方的矩形的两侧必须都超出中间的矩形否则将被误解成T, L, J\text{T, L, J}T, L, J等字母。例如这是两个合法的I\text{I}I型颁奖台而以下三种情况均不合法希望你编程寻找面积最大的I\text{I}I型颁奖台使其不覆盖任何展示台。输入格式第一行包含两个正整数n, mn,\,mn,m分别表示 YONG-IN Hall 的矩形网格区域的行数和列数。以下nnn行每行包含mmm个数字pi, jp_{i,\,j}pi,j​每个数字描述一个单位网格111表示该单位网格存在展示台000表示该单位网格不存在展示台。输出格式仅包含一个正整数表示最大的I\text{I}I型颁奖台的面积。如果不存在合法的I\text{I}I型颁奖台则输出000。输入输出样例 #1输入 #16 8 1 1 1 1 1 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 1输出 #115说明/提示对于100%100\%100%的数据1≤n, m≤2001 \leq n,\,m \leq 2001≤n,m≤200pi, j∈{0, 1}p_{i,\,j} \in \{0,\,1\}pi,j​∈{0,1}。样例解释可选出的最大I\text{I}I型颁奖台面积为151515。C实现#includebits/stdc.husingnamespacestd;constintNR210;#defineintlonglongintn,m,ans;intf[2][NR][NR][4];intg[NR][NR][3];intsum[NR][NR];intx;signedmain(){cinnm;for(inti1;in;i)for(intj1;jm;j){cinx;sum[i][j]sum[i][j-1]x;}memset(f,-999999,sizeof(f));memset(g,-999999,sizeof(g));for(inti1;in;i){memset(f[x],-999999,sizeof(f[x]));for(intl3;l0;l--){for(intj1;jm;j)for(intkj;km;k)if(sum[i][k]sum[i][j-1]){if(l1)f[x^1][j][k][1]max(f[x^1][j][k][1],0ll);f[x][j][k][l]f[x^1][j][k][l]k-j1;if(l2)f[x][j][k][2]max(g[j-1][k1][1]k-j1,f[x][j][k][2]);if(l3)f[x][j][k][3]max(g[j1][k-1][2]k-j1,f[x][j][k][3]);}if(l1)for(intj1;jm;j)for(intkm;kj;k--)g[j][k][1]max(f[x][j][k][1],max(g[j-1][k][1],g[j][k1][1]));if(l2)for(intjm;j1;j--)for(intkj;km;k)g[j][k][2]max(f[x][j][k][2],max(g[j1][k][2],g[j][k-1][2]));if(l3)for(intj1;jm;j)for(intk1;km;k)ansmax(ans,f[x][j][k][3]);}x^1;}coutansendl;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容