SCP-bzoj-1084

项目编号：bzoj-1084

项目等级：Safe

项目描述：

　　戳这里

特殊收容措施：

　　分类讨论+DP。#滑稽

　　预处理前缀和s[i][s]=Σa[j][s](∀j∈[1,i])（m=1时略去第二维）

　　对于m=1，设计状态f[i][j]表示前i列中已选取j个矩形的最大分值。转移方程f[i][j]=max(f[i-1][j-1],max{f[k][j-1]+s[i]-s[k-1]})。

　　对于m=2，设计状态f[i][j][k]表示第一行前i列中、第二行前j列中已选取k个矩形的最大分值。有三种转移方式：

　　•传递性转移：max(f[i-1][j][k],f[i][j-1][k])->f[i][j][k]

　　•单行转移：max(max{f[x][j][k-1]+s[i][0]-s[x-1][0]},max{f[i][x][k]+s[j][1]-s[x-1][1]})->f[i][j][k]

　　•双行转移（前提：i=j）：max{f[x][x][k-1]+s[i][0]-s[x-1][0]+s[j][1]-s[x-1][1]}->f[i][j][k]

　　复杂度O(n⁴)。

附录：

 1 #include <bits/stdc++.h>
 2 #define range(i,c,o) for(register int i=(c);i<(o);++i)
 3 #define dange(i,c,o) for(register int i=(c);i>(o);--i)
 4 using namespace std;
 5 
 6 //#define __debug
 7 #ifdef __debug
 8     #define def(t) t
 9 #else
10     #define def(t) __attribute__((optimize("-O2"))) inline t
11 #endif
12 
13 // quick_io BEGIN HERE
14 def(int) getI()
15 {
16     char c=getchar(); int r=0; short s=1;
17     for(;!isdigit(c)&&c!='-';c=getchar());
18     for(;c=='-';c=getchar()) s*=-1;
19     for(;isdigit(c);c=getchar()) r=(r<<3)+(r<<1)+c-'0';
20     return s*r;
21 }
22 // quick_io END HERE
23 
24 static int N=getI(),M=getI(),K=getI();
25 int s[105][2],a[105][2],f[105][105][2];
26 def(int) solve1()
27 {
28     range(i,1,N+1) s[i][0]=s[i-1][0]+a[i][0];
29     bool cur=1;
30     range(k,0,K)
31     {
32         cur^=1;
33         range(i,1,N+1)
34         {
35             f[i][0][cur]=f[i-1][0][cur];
36             range(j,0,i) f[i][0][cur]=max(
37                 f[i][0][cur],
38                 f[j][0][cur^1]+s[i][0]-s[j][0]
39             );
40         }
41     }
42     return f[N][0][cur];
43 }
44 def(int) solve2()
45 {
46     range(i,1,N+1) range(j,0,2) s[i][j]=s[i-1][j]+a[i][j];
47     bool cur=1;
48     range(k,0,K)
49     {
50         cur^=1;
51         range(i,1,N+1) range(j,1,N+1)
52         {
53             f[i][j][cur]=max(f[i-1][j][cur],f[i][j-1][cur]);
54             range(x,0,i) f[i][j][cur]=max(
55                 f[i][j][cur],f[x][j][cur^1]+s[i][0]-s[x][0]
56             );
57             range(x,0,j) f[i][j][cur]=max(
58                 f[i][j][cur],f[i][x][cur^1]+s[j][1]-s[x][1]
59             );
60             if(i==j) range(x,0,i) f[i][j][cur]=max(
61                 f[i][j][cur],
62                 f[x][x][cur^1]+s[i][0]-s[x][0]+s[j][1]-s[x][1]
63             );
64         }
65     }
66     return f[N][N][cur];
67 }
68 
69 int main()
70 {
71     range(i,1,N+1) range(j,0,M) a[i][j]=getI();
72     return printf("%d
",M&1?solve1():solve2()),0;
73 }

View Code