P1295-创意吃鱼

输入输出格式

emmmm，刚看到这道题，这不是很显然吗，用f[i][j]表示以(i，j)为正方形的右下角所满足题意的最大正方形的边长，则转移方程为

```if(a[i][j] == 1) {
int x = f[i - 1][j - 1];
int x1 = i - x, y1 = j - x;
if(sum[i][j] - sum[x1 - 1][j] - sum[i][y1 - 1] + sum[x1 - 1][y1 - 1] == x + 1) {
f[i][j] = x + 1;
}
}```

两天后......

```#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 5e5 + 100;
const int MAXM = 3e3 + 10;

template < typename T > inline void read(T &x) {
x = 0; T ff = 1, ch = getchar();
while(!isdigit(ch)) {
if(ch == ‘-‘) ff = -1;
ch = getchar();
}
while(isdigit(ch)) {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x *= ff;
}

template < typename T > inline void write(T x) {
if(x < 0) putchar(‘-‘), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + ‘0‘);
}

int n, m, maxx = -INF, a[MAXM][MAXM], b[MAXM][MAXM], sum[MAXM][MAXM], f[MAXM][MAXM];

int main() {
//    freopen("1.in", "r", stdin);
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
}
}

/*    for(int len = 1; len <= min(n, m); ++len) {
for(int i = 1; i <= n - len + 1; ++i) {
for(int j = 1; j <= m - len + 1; ++j) {
int x1 = i + len - 1;
int y1 = j + len - 1;
if(sum[x1][y1] - sum[i - 1][y1] - sum[x1][j - 1] + sum[i - 1][j - 1] != len * len) continue;

}
}
}*/
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(a[i][j] == 1) {
int x = f[i - 1][j - 1];
for(int k = x; k >= 0; --k) {
int x1 = i - k, y1 = j - k;
if(sum[i][j] - sum[x1 - 1][j] - sum[i][y1 - 1] + sum[x1 - 1][y1 - 1] == k + 1) {
f[i][j] = k + 1;
break;
}
}
}
maxx = max(maxx, f[i][j]);
}
}
//    memset(sum, 0, sizeof(sum));
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
b[i][j] = a[i][m - j + 1];
//            sum[i][j] = sum[i][m - j + 1];
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + b[i][j];
}
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(b[i][j] == 1) {
int x = f[i - 1][j - 1];
for(int k = x; k >= 0; --k) {
int x1 = i - k, y1 = j - k;
if(sum[i][j] - sum[x1 - 1][j] - sum[i][y1 - 1] + sum[x1 - 1][y1 - 1] == k + 1) {
f[i][j] = k + 1;
break;
}
}
}
maxx = max(maxx, f[i][j]);
}
}
write(maxx);
putchar(‘\n‘);
return 0;
}```

每一个你不满意的现在，都有一个你没有努力的曾经。
一个历史类的公众号，欢迎关注