首页 > 代码库 > 計蒜客/數正方形(dp)
計蒜客/數正方形(dp)
題目鏈接:https://nanti.jisuanke.com/t/44
題意:中文題誒~
思路: 用dp[i][j]存儲以(i, j)爲左上定點的最大正方形變長,從右下角網左上角一次計算所有頂點;
通過畫圖不難分析出動態專題方程式爲:
dp[i][j]=min(dp[i+1][j+1], dp[i+1][j], dp[i][j+1]) + 1
需要注意的是如何累計所有變長的正方形數目, 對於坐標(i, j), 從2~dp[i][j]依次累加一次即可;
代碼:
1 #include <iostream> 2 #include <stdio.h> 3 using namespace std; 4 5 const int MAXN=250+10; 6 char a[MAXN][MAXN]; 7 int dp[MAXN][MAXN];//dp[i][j]存儲以i,j爲左上定點的最大正方形 8 int vis[MAXN]; 9 10 int main(void){ 11 int n; 12 scanf("%d", &n); 13 for(int i=0; i<n; i++){ 14 scanf("%s", a[i]); 15 } 16 for(int i=n-1; i>=0; i--){ 17 for(int j=n-1; j>=0; j--){ 18 if(a[i][j]-‘0‘){ 19 dp[i][j]=min(dp[i+1][j+1], min(dp[i][j+1], dp[i+1][j]))+1; 20 } 21 for(int k=2; k<=dp[i][j]; k++){//累計變長爲k的正方形數目 22 vis[k]++; 23 } 24 } 25 } 26 for(int i=2; i<=n; i++){ 27 if(vis[i]){ 28 printf("%d %d\n", i, vis[i]); 29 } 30 } 31 return 0; 32 }
計蒜客/數正方形(dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。