atcoder ABC311 E - Defect-free Squaresの勉強

atcoder DP

atcoder.jp

・参考
AtCoder ABC 311 E - Defect-free Squares (水色, 475 点) - けんちょんの競プロ精進記録

・説明
　dp[i+1][j+1]のi+1,j+1はSのi,jマスの最大辺である。また参考記事の場合、indexを合わせるなら,for (i=1;i<=H;++i); for(j=1;j<=W;++j); dp[i][j]=min({dp[i-1][j-1],dp[i][j-1],dp[i-1][j]})とすればよい。ここでminの意味はアルゴリズム入門講座: 最大正方形問題の動的計画法による解法と考え方の図を参照。
　集計は例えば穴の無いマスが2*2あるとき、dp[1][1](1行目、１列)=1,　dp[1][2]=1,　dp[2][1]=1,　dp[2][2]=2となり、穴のないマスは5となる。

h,w,n=map(int,input().split())
field=[[0 for _ in range(w)]for _ in range(h)]

#穴の場所を1にする。
for i in range(n):
  a,b=map(int,input().split())
  field[a-1][b-1]=1

dp=[[0 for _ in range(w+1)]for _ in range(h+1)]  #i,jは0インデックスではない。i,j=0,0でなくi,jの1,1は1行目１列を表す。

for i in range(h):
  for j in range(w):
    if field[i][j]==0:
      dp[i+1][j+1]=min(dp[i][j],dp[i+1][j],dp[i][j+1])+1
      
#集計する。最大辺がその頂点を右下隅とする正方形の個数になる。     
ans=0
for i in range(h):
  for j in range(w):
    ans+=dp[i+1][j+1]
print(ans)