把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

CF1580A Portals
给一个大小为n*m(都小于等于400)的棋盘，分为0和1，你可以进行任意次操作，每次将一个0变成1或者1变成0，然后你需要得到一个传送门
形状如下
111
10001
111
角的材质任意，边必须是1，中间必须是0，大小任意，求获得一个传送门最小需要的操作数量。

解：

第一眼看这题人是麻的，你光让我找一个传送门出来我都不一定找得到……
首先既然传送门大小是任意的，那么高和宽我肯定要规定一个，将二维转化为一维，这是做形状为正方形的题目时的经验之一。
在这里我选择了去决定高度，也就是建立一个二层循环定下决定高度的两点，而接下来我就只能再允许O(n)的复杂度了……
假设高度确定的情况下我从头开始去建立一个宽度为k的传送门，我可以依靠预处理线段来快速求得我所需要的操作数量，这个时候你会发现，你需要的传送门其实是一个连续的段，而你要求的是最小段和，咱一直求的都是最大段和啥时候求过最小段和啊。因此我们可以倒过来求，首先求出建一个最大的传送门所需要的步数，然后让子段去代表将其还原为原来所需要的步数，实际上求出的也就是能够省下的步数，这样要求的就变成了最大子段和，用通常的lis就可以完成，值得注意的是由于题目中奇葩的传送门定义，边界判断变得异常恶心，思路乱掉的时候一定要先在纸上把思路捋清楚，做好前缀和再去写状态转移方程。
实际上这题由于求的传送门是一个规则的长方形所以做起来没有那么麻烦，那要是之后让我求个三角形啊菱形怎么办呢？不管怎么说，对于形状固定的二维操作，最先进行的都是降维，之后的最优想办法转化为子问题或者经典的子段模型，船到桥头自然直。
那么Portal2，将题中的长方形改为菱形吧！
属于是开创一门新的形状DP了。

代码

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <cstring>
#include <string>
#define ll long long
#define maxn 200005
#define mdl 1000000007
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
using namespace std;
char str[405][405];
int ones[405][405], dp[405][405];
int cnt(int x1, int y1, int x2, int y2) {
	return ones[x2][y2] - ones[x2][y1 - 1] - ones[x1 - 1][y2] + ones[x1 - 1][y1 - 1];
}
int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		int n, m, i, j, k, ans = 1e9;
		scanf("%d%d", &n, &m);
		for (int i = 0; i < n; i++)scanf("%s", str[i]);
		for (i = 1; i <= n; i++) {
			for (j = 1; j <= m; j++) {
				ones[i][j] = ones[i - 1][j] + ones[i][j - 1] - ones[i - 1][j - 1];
				if (str[i - 1][j - 1] == '1') {
					ones[i][j]++;
				}

			}
		}
	
		for (i = 1; i <= n; i++) {
			for (j = i + 4; j <= n; j++) {
				for (k = 4; k <= m; k++) {
					dp[j][k] = cnt(i + 1, 1, j - 1, k - 1) + k - 2 - cnt(i, 2, i, k - 1) + k - 2 - cnt(j, 2, j, k - 1) + j - i - 1 - cnt(i + 1, k, j - 1, k);
				}
				for (k = m - 1; k >= 4; k--) {
					dp[j][k] = min(dp[j][k], dp[j][k + 1]);
				}
				for (k = 1; k <= m - 3; k++) {
					int tmp;
					if(k==1)tmp = dp[j][k + 3] - cnt(i + 1, 1, j - 1, k) + j - i - 1 - cnt(i + 1, k, j - 1, k);
					else  tmp = dp[j][k + 3] - cnt(i + 1, 1, j - 1, k) -(k-1- cnt(i, 2, i, k)) -(k-1- cnt(j, 2, j, k)) + j - i - 1 - cnt(i + 1, k, j - 1, k);
					if (tmp < ans) {
						//cout << i << "." << j << "." << k<<"."<<dp[j][k+3] << endl;
						ans = tmp;
					}
				}
			}
		}
		printf("%d\n", ans);
	}
}