uoj 125 书法家

发表于 | 更新于

Link

Solution

第一步转化是最重要的：把所有的图形都转化为纵向的几部分，然后分11种情况转移即可 细节不算很多，而且样例给的比较良心 唯一想写一下的是NN的第2种转移。 大体是这样的形式: f(i,l,r)=min{f(i−1,p,q)∣p∈[l,r+1],q∈[r,n]}+Sum(i,l,r)f(i,l,r)=\min \{f(i-1,p,q)|p\in [l,r+1],q\in[r,n]\}+Sum(i,l,r) 这个转移做到O(1)O(1)对我这种juruo还是比较有难度的。。 想了很长时间都不对，只好看Fuxey神的题解，虽然没有看懂，但得到了一个很好的思路：数形结合 于是用几何画板画出来。 (最后面划的那几下是表明以此类推。。) 然后就很清晰了，只要维护每一竖列的最大值，就可以更新了。

Tips

涉及到不等关系的各种东西，如果想不明白，就画图，画几个连续变化的图感受一下。

Code

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
//Code by Lucida
#include<bits/stdtr1c++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
#define Reset(x) memset(x,170,sizeof(x))
typedef long long int64;
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
using std::max;
using std::min;
using std::partial_sum;
const int MAXN=150+11,MAXM=500+11,INF=-0xAAAAAAAA;
int a[MAXM][MAXN],pref[MAXM][MAXN],n,m;
int Sum(int x,int l,int r){return pref[x][r]-pref[x][l-1];}
int Pool[2][MAXM][MAXN][MAXN],Me=0,(*f)[MAXN][MAXN],(*pre)[MAXN][MAXN],g[3][MAXM];
void Alloc(){pre=f;f=Pool[Me^=1];Reset(Pool[Me]);}
void N()
{	
	Alloc();
	for(int i=1;i<=m;++i)
		for(int l=1;l<=n;++l)
			for(int r=l;r<=n;++r)
				f[i][l][r]=max(f[i-1][l][r],0)+Sum(i,l,r);
	Alloc();
	for(int i=2;i<=m;++i)
		for(int l=1;l<=n;++l)
			for(int r=l;r<=n;++r)
				f[i][l][r]=max(pre[i-1][l-1][r]+Sum(i,l,r),f[i][l-1][r]-a[i][l-1]);
	
	int *mx=g[0];
	for(int i=3;i<=m;++i)
	{
		Reset(g[0]);
		for(int r=n;r>=1;--r)
		{
			for(int l=r,maxv=mx[r+1];l>=1;--l)
			{
				chkmx(mx[l],f[i-1][l][r]);
				chkmx(maxv,mx[l]);
				chkmx(f[i][l][r],maxv+Sum(i,l,r));
			}
		}
	}
	Alloc();
	for(int i=3;i<=m;++i)
		for(int l=1;l<=n;++l)
			for(int r=l;r<=n;++r)	
				f[i][l][r]=max(pre[i-1][l][r-1]+Sum(i,l,r),f[i][l][r-1]+a[i][r]);
	for(int i=4;i<=m;++i)
		for(int l=1;l<=n;++l)
			for(int r=l;r<=n;++r)
				chkmx(f[i][l][r],f[i-1][l][r]+Sum(i,l,r));
	Reset(g[0]);
	for(int i=3;i<=m;++i)
		for(int l=1;l<=n;++l)
			for(int r=l;r<=n;++r)
				chkmx(g[0][i],f[i][l][r]);
}
void O()
{
	Alloc();
	for(int i=5;i<=m;++i)
		for(int l=1;l<=n;++l)
			for(int r=l;r<=n;++r)
				f[i][l][r]=max(g[0][i-2],f[i-1][l][r]-Sum(i-1,l,r))+Sum(i,l,r);
	Alloc();
	for(int i=6;i<=m;++i)
		for(int l=1;l<=n;++l)
			for(int r=l+2;r<=n;++r)
				f[i][l][r]=max(pre[i-1][l][r],f[i-1][l][r])+a[i][l]+a[i][r];
	Alloc();
	for(int i=7;i<=m;++i)
		for(int l=1;l<=n;++l)
			for(int r=l;r<=n;++r)
				f[i][l][r]=pre[i-1][l][r]+Sum(i,l,r);
	Reset(g[1]);
	for(int i=7;i<=m;++i)
		for(int l=1;l<=n;++l)
			for(int r=l;r<=n;++r)
				chkmx(g[1][i],f[i][l][r]);

}
void I()
{
	Alloc();
	for(int i=9;i<=m;++i)
		for(int l=1;l<=n;++l)
			for(int r=l+2;r<=n;++r)
				f[i][l][r]=max(g[1][i-2],f[i-1][l][r]-a[i-1][l]-a[i-1][r])+a[i][l]+a[i][r];
	for(int i=10;i<=m;++i)
		for(int l=1;l<=n;++l)
			for(int r=l+2;r<=n;++r)
				chkmx(f[i][l][r],f[i-1][l][r]+a[i][l]+a[i][r]);
	Alloc();
	for(int i=10;i<=m;++i)
		for(int l=1;l<=n;++l)
			for(int r=l;r<=n;++r)
				f[i][l][r]=max(f[i-1][l][r],pre[i-1][l][r])+Sum(i,l,r);
	Alloc();
	for(int i=11;i<=m;++i)
		for(int l=1;l<=n;++l)
			for(int r=l;r<=n;++r)
				f[i][l][r]=max(pre[i-1][l][r],f[i-1][l][r])+a[i][l]+a[i][r];
	Reset(g[2]);
	for(int i=11;i<=m;++i)
		for(int l=1;l<=n;++l)
			for(int r=l;r<=n;++r)
				chkmx(g[2][i],f[i][l][r]);
}
int P()
{
	int Ans=-INF;
	for(int i=11;i<=m;++i)
		chkmx(Ans,g[2][i]);
	return Ans;
}
int main()
{
	get(n),get(m);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			get(a[j][n-i+1]);
	for(int j=1;j<=m;++j)
		partial_sum(a[j]+1,a[j]+1+n,pref[j]+1);
	N(),O(),I();
	int Ans=P();
	put(Ans),putchar('\n');
	return 0;
}