首页 > 代码库 > bzoj1084题解
bzoj1084题解
【解题思路】
分类讨论+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(n4)。
【参考代码】
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 #else10 #define def(t) __attribute__((optimize("-O2"))) inline t11 #endif12 13 // quick_io BEGIN HERE14 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 HERE23 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\n",M&1?solve1():solve2()),0;73 }
bzoj1084题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。