{"id":501,"date":"2020-05-15T10:40:24","date_gmt":"2020-05-15T02:40:24","guid":{"rendered":"http:\/\/www.zyhcoding.club\/?p=501"},"modified":"2020-05-17T15:27:30","modified_gmt":"2020-05-17T07:27:30","slug":"5-14%e8%a1%a5%e9%a2%98-%e7%ac%ac9%e6%ac%a1%e8%ae%ad%e7%bb%83","status":"publish","type":"post","link":"http:\/\/www.zyhcoding.club\/index.php\/2020\/05\/15\/5-14%e8%a1%a5%e9%a2%98-%e7%ac%ac9%e6%ac%a1%e8%ae%ad%e7%bb%83\/","title":{"rendered":"5-14\u8865\u9898 \u7b2c\u4e5d\u6b21\u8bad\u7ec3"},"content":{"rendered":"

\u52a8\u6001\u89c4\u5212 \u7b2c\u4e5d\u6b21\u8bad\u7ec3<\/a> dp\u7efc\u5408<\/h3>\n

\"\"<\/p>\n

C Counting Rectangles is Fun<\/a><\/h4>\n

\u9898\u610f\uff1a\u7ed9\u5b9a\u4e00\u4e2anm\u768401\u77e9\u9635\uff0cq\u6b21\u8be2\u95ee\uff0c\u6bcf\u6b21\u8be2\u95ee\u4e3a4\u4e2a\u6574\u6570a,b,c,d\uff0c\u8f93\u51fa\u4ee5\u5de6\u4e0a\u9876\u70b9\u4e3a(a,b)\uff0c\u53f3\u4e0b\u9876\u70b9\u4e3a(c,d)\u7684\u77e9\u9635\u5185\u7684\u201c\u597d\u77e9\u9635\u201d\u7684\u4e2a\u6570\u3002
\n\u597d\u77e9\u9635\uff1a\u53ea\u5305\u542b0\u7684\u77e9\u9635\u3002<\/p>\n

\u7528\u56db\u5143\u7ec4(a,b,c,d)\u6765\u8868\u793a\u4e00\u4e2a\u77e9\u9635\u3002
\n\u4e8c\u7ef4dp\uff0c\u8bbe
\ndp1[a][b][c][d]\u8868\u793a(a,b,c,d)\u8fd9\u4e2a\u77e9\u9635\u4ee5(c,d)\u4e3a\u53f3\u4e0b\u9876\u70b9\u7684\u201c\u597d\u77e9\u5f62\u201d\u4e2a\u6570
\ndp2[a][b][c][d]\u8868\u793a(a,b,c,d)\u8fd9\u4e2a\u77e9\u9635\u5185\u7684\u201c\u597d\u77e9\u5f62\u201d\u4e2a\u6570
\nrow[i][j]\u8868\u793a\u4ee5(i,j)\u7ed3\u5c3e\u7684\u5f62\u72b6\u4e3a1*m<\/code>\u7684\u201c\u597d\u77e9\u5f62\u201d\u4e2a\u6570
\ncol[i][j]\u8868\u793a\u4ee5(i,j)\u7ed3\u5c3e\u7684\u5f62\u72b6\u4e3am*1<\/code>\u7684\u201c\u597d\u77e9\u5f62\u201d\u4e2a\u6570<\/p>\n

\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b
\ndp1[a][b][c][d] = dp1[max(a,c-col[c][d]+1)][max(b,d-row[c][d]+1)][c-1][d-1] + min(col[c][d], c-a+1) + min(row[c][d], d-b+1) - 1;<\/code>
\ndp2[a][b][c][d] = dp2[a][b][c][d-1] + dp2[a][b][c-1][d] - dp2[a][b][c-1][d-1] + dp1[a][b][c][d];<\/code>
\n\u65f6\u95f4\u590d\u6742\u5ea6O(n^2m^2+q)<\/code><\/strong>
\n\uff08\u603b\u89c9\u5f97\u8fd9\u9898\u6211\u505a\u7684\u9ebb\u70e6\u4e86\uff0c\u7f51\u4e0a\u770b\u4e86\u522b\u7684\u4ee3\u7801\u90fd\u633a\u7b80\u5355\uff0c\uff0c<\/p>\n

#include <cstdio>\n#include <cstring>\n#include <algorithm>\nusing namespace std;\nint n, m, q;\nchar s[50][50];\nint row[50][50], col[50][50];\nint dp1[50][50][50][50];\nint dp2[50][50][50][50];\nvoid init();\nint main(){\n    scanf ("%d %d %d", &n, &m, &q);\n    for (int i=1;i<=n;i++)  scanf ("%s", s[i]+1);\n    init();\n    while (q--){\n        int a, b, c, d;\n        scanf ("%d %d %d %d", &a, &b, &c, &d);\n        printf ("%d\\n", dp2[a][b][c][d]);\n    }\n    return 0;\n}\n\nvoid init(){\n    for (int i=1;i<=n;i++){\n        if (s[i][1]=='0')    row[i][1] = 1;\n        for (int j=2;j<=m;j++)\n            if (s[i][j]=='0')\n                row[i][j] = row[i][j-1] + 1;\n    }\n    for (int j=1;j<=m;j++){\n        if (s[1][j]=='0')    col[1][j] = 1;\n        for (int i=2;i<=n;i++)\n            if (s[i][j]=='0')\n                col[i][j] = col[i-1][j] + 1;\n    }\n    for (int a=n;a>=1;a--){\n        for (int b=m;b>=1;b--){\n            for (int d=b;d<=m;d++)  dp1[a][b][a][d] = min(row[a][d], d-b+1);\n            for (int c=a;c<=n;c++)  dp1[a][b][c][b] = min(col[c][b], c-a+1);\n            for (int c=a+1;c<=n;c++){\n                for (int d=b+1;d<=m;d++)  if (s[c][d]=='0'){\n                    dp1[a][b][c][d] = dp1[max(a,c-col[c][d]+1)][max(b,d-row[c][d]+1)][c-1][d-1] + min(col[c][d], c-a+1) + min(row[c][d], d-b+1) - 1;\n                }\n            }\n        }\n    }\n    for (int a=1;a<=n;a++){\n        for (int b=1;b<=m;b++){\n            for (int c=a;c<=n;c++){\n                for (int d=b;d<=m;d++){\n                    dp2[a][b][c][d] = dp2[a][b][c][d-1] + dp2[a][b][c-1][d] - dp2[a][b][c-1][d-1] + dp1[a][b][c][d];\n                }\n            }\n        }\n    }\n    return;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u52a8\u6001\u89c4\u5212 \u7b2c\u4e5d\u6b21\u8bad\u7ec3 dp\u7efc\u5408 C Counting Rectangles is Fun \u9898\u610f\uff1a\u7ed9\u5b9a […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[31],"tags":[],"_links":{"self":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/501"}],"collection":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/comments?post=501"}],"version-history":[{"count":10,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/501\/revisions"}],"predecessor-version":[{"id":541,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/501\/revisions\/541"}],"wp:attachment":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/media?parent=501"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/categories?post=501"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/tags?post=501"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}