\(\\\)
给出一个\(N\times M\)的有权矩阵，选出其中\(K\)个互不重叠的子矩阵，使得这\(K\)个子矩阵的权值和最大。
- \(N\in [1,100]\)，\(M\in \{1,2\}\)，\(K\in [1,10]\)
\(\\\)
\(Solution\)
- 对于\(M=1\)的情况，矩阵是一个长为\(N\)的数列，问题变为\(K\)段最大子段和，可以参考：。
- 对于\(M=2\)的情况，沿用上一情况的做法，设状态\(f[i][j][S]\)表示当前处理到第\(i\)行，已经选了\(j\)个子矩阵，本行选则方式为\(S\)的方案数。
- 分析情况可知，\(S\)有一下五种：
- \(0\)：两个位置都不选
- \(1\)：只选左边的元素
- \(2\)：只选右边的元素
- \(3\)：两个都选，放在一个矩形里
- \(4\)：两个都选，放在两个矩形里
- 对五种状态分别讨论转移即可：
- \(0\)状态无需考虑任何限制，直接从上一行的五种状态转移：\(\begin{align}f[i][j][0]=max\{f[i-1][j][0/1/2/3/4]\}\end{align}\)
- \(1\)状态只能从\(1\)状态和\(4\)状态直接继承，其他都得从上一个矩形转移：\(\begin{align}f[i][j][1]=a[i][0]+max\{f[i-1][j-1][0/2/3],f[i-1][j][1/4]\}\end{align}\)
- \(2\)状态只能从\(2\)状态和\(4\)状态直接转移，其他都得从上一个矩形转移：\(\begin{align}f[i][j][2]=a[i][1]+max\{f[i-1][j-1][0/1/3],f[i-1][j][2/4]\}\end{align}\)
- \(3\)状态只能从\(3\)状态直接转移，定义\(s[i]=a[i][0]+a[i][1]\)：\(\begin{align}f[i][j][3]=s[i]+max\{f[i-1][j-1][0/1/2/4],f[i-1][j][3]\}\end{align}\)
- \(4\)状态只能直接从\(4\)状态转移，但是可以利用\(1\)状态和\(2\)状态的矩阵：\(\begin{align}f[i][j][4]=s[i]+max\{f[i-1][j-2][0/3],f[i-1][j-1][1/2],f[i-1][j][4]\}\end{align}\)
- 需要注意的是，初始化只有所有的\(0\)状态为\(0\)，其他应该是\(-\infty\)，防止一些转移的初始状态不存在。
\(\\\)
\(Code\)
#include#include #include #include #include #include #include #define N 110#define K 15#define R register#define gc getcharusing namespace std;inline int rd(){ int x=0; bool f=0; char c=gc(); while(!isdigit(c)){if(c=='-')f=1;c=gc();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();} return f?-x:x;}int n,m,k,a[N][2],f[N][K][5];inline void work1(){ for(R int i=1;i<=n;++i) a[i][0]=rd(); for(R int i=1;i<=n;++i) for(R int j=1;j<=min(i,k);++j){ f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]); f[i][j][1]=a[i][0]+max(f[i-1][j][1],max(f[i-1][j-1][0],f[i-1][j-1][1])); } printf("%d\n",max(f[n][k][1],f[n][k][0]));};inline int mx(int a,int b,int c,int d,int e){ return max(max(a,b),max(max(c,d),e));}inline void work2(){ memset(f,0xcf,sizeof(f)); for(R int i=0;i<=n;++i) for(R int j=0;j<=k;++j) f[i][j][0]=0; for(R int i=1;i<=n;++i){a[i][0]=rd();a[i][1]=rd();} for(R int i=1;i<=n;++i) for(R int j=1;j<=k;++j){ f[i][j][0]=mx(f[i-1][j][0],f[i-1][j][1],f[i-1][j][2],f[i-1][j][3],f[i-1][j][4]); f[i][j][1]=a[i][0]+mx(f[i-1][j][1],f[i-1][j][4],f[i-1][j-1][0],f[i-1][j-1][2],f[i-1][j-1][3]); f[i][j][2]=a[i][1]+mx(f[i-1][j][2],f[i-1][j][4],f[i-1][j-1][0],f[i-1][j-1][1],f[i-1][j-1][3]); f[i][j][3]=a[i][0]+a[i][1]+mx(f[i-1][j][3],f[i-1][j-1][0],f[i-1][j-1][1],f[i-1][j-1][2],f[i-1][j-1][4]); f[i][j][4]=a[i][0]+a[i][1]+max(f[i-1][j][4],max(f[i-1][j-1][1],f[i-1][j-1][2])); if(j>=2) f[i][j][4]=max(f[i][j][4],a[i][0]+a[i][1]+max(f[i-1][j-2][0],f[i-1][j-2][3])); } printf("%d\n",mx(f[n][k][0],f[n][k][1],f[n][k][2],f[n][k][3],f[n][k][4]));};int main(){ n=rd(); m=rd(); k=rd(); (m==1)?work1():work2(); return 0;}