I-区域

有生之年,敲这么长的dp代码,记录一下~

//一题不会是真的.
#include <bits/stdc++.h>
using namespace std;
//f(i,j,l,r,k1,k2)//到了第几行 选了几个数 选的数的左端点 右端点是什么 左端点是递增/递减 右端点是递增/递减
int f[16][16*16][16][16][2][2];

int sum[16][16],x;
struct vv{
  int a,b;
};
struct node{
    int aa,ab,ac,ad,ae,af;
}pre[16][16*16][16][16][2][2];
node t;
vector<vv>v;
int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&x);
            sum[i][j]+=sum[i][j-1]+x;//记录下前缀嘛
        }
    }
    //开始DP
    /*
    先写DP方程:(0表示递增 1表示递减)
    if(j>=(r-l+1)&&l1<=l&&r>=l&&r1>=r)
    0 0->1 1    f[i][j][l][r][1][1]=max(f[i][j][l][r][1][1],f[i-1][j-(r-l+1)][l1][r1][0][0]+sum[i][r]-sum[i][l-1]);
    if(j>=(r-l+1)&&l1<=l&&l<=r1&&r>=r1)
    0 0->1 0    f[i][j][l][r][1][0]=max(f[i][j][l][r][1][0],f[i-1][j-(r-l+1)][l1][r1][0][0]+sum[i][r]-sum[i][l-1]);
    if(j>=(r-l+1)&&l<=l1&&r>=l1&&r1>=r)
    0 0->0 1    f[i][j][l][r][0][1]=max(f[i][j][l][r][0][1],f[i-1][j-(r-l+1)][l1][r1][0][0]+sum[i][r]-sum[i][l-1]);
    if(j>=(r-l+1)&&l<=l1&&l1<=r1&&r1<=r)
    0 0->0 0    f[i][j][l][r][0][0]=max(f[i][j][l][r][0][0],f[i-1][j-(r-l+1)][l1][r1][0][0]+sum[i][r]-sum[i][l-1]);
    if(j>=(r-l+1)&&l1<=l&&r>=l&&r1>=r)
    1 1->1 1    f[i][j][l][r][1][1]=max(f[i][j][l][r][1][1],f[i-1][j-(r-l+1)][l1][r1][1][1]+sum[i][r]-sum[i][l-1]);
    if(j>=(r-l+1)&&l1<=l&&r>=l&&r1>=r)
    1 0->1 1    f[i][j][l][r][1][1]=max(f[i][j][l][r][1][1],f[i-1][j-(r-l+1)][l1][r1][1][0]+sum[i][r]-sum[i][l-1]);
    if(j>=(r-l+1)&&l1<=l&&l<=r1&&r>=r1)
    1 0->1 0    f[i][j][l][r][1][0]=max(f[i][j][l][r][1][0],f[i-1][j-(r-l+1)][l1][r1][1][0]+sum[i][r]-sum[i][l-1]);
    if(j>=(r-l+1)&&l1<=l&&r>=l&&r1>=r)
    0 1->1 1    f[i][j][l][r][1][1]=max(f[i][j][l][r][1][1],f[i-1][j-(r-l+1)][l1][r1][0][1]+sum[i][r]-sum[i][l-1]);
    if(j>=(r-l+1)&&l<=l1&&r>=l1&&r1>=r)
    0 1->0 1    f[i][j][l][r][0][1]=max(f[i][j][l][r][0][1],f[i-1][j-(r-l+1)][l1][r1][0][1]+sum[i][r]-sum[i][l-1]);
    */
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=k;j++)
        {
           for(int l=1;l<=m;l++)
           {
               for(int r=l;r<=m;r++)
               {
                   for(int l1=1;l1<=m;l1++)
                   {
                       for(int r1=1;r1<=m;r1++)
                       {
                        if(j>=(r-l+1)&&l1<=l&&r>=l&&r1>=r)
                        {
                            if(f[i-1][j-(r-l+1)][l1][r1][0][0]+sum[i][r]-sum[i][l-1]>f[i][j][l][r][1][1])
                            {
                                 f[i][j][l][r][1][1]=f[i-1][j-(r-l+1)][l1][r1][0][0]+sum[i][r]-sum[i][l-1];
                                 pre[i][j][l][r][1][1]={i-1,j-(r-l+1),l1,r1,0,0};
                            }
                        }
                        if(j>=(r-l+1)&&l1<=l&&l<=r1&&r>=r1)
                        {
                            if(f[i-1][j-(r-l+1)][l1][r1][0][0]+sum[i][r]-sum[i][l-1]>f[i][j][l][r][1][0])
                            {
                                 f[i][j][l][r][1][0]=f[i-1][j-(r-l+1)][l1][r1][0][0]+sum[i][r]-sum[i][l-1];
                                 pre[i][j][l][r][1][0]={i-1,j-(r-l+1),l1,r1,0,0};
                            }
                        }
                        if(j>=(r-l+1)&&l<=l1&&r>=l1&&r1>=r)
                        {
                            if(f[i-1][j-(r-l+1)][l1][r1][0][0]+sum[i][r]-sum[i][l-1]>f[i][j][l][r][0][1])
                            {
                                 f[i][j][l][r][0][1]=f[i-1][j-(r-l+1)][l1][r1][0][0]+sum[i][r]-sum[i][l-1];
                                 pre[i][j][l][r][0][1]={i-1,j-(r-l+1),l1,r1,0,0};
                            }
                        }
                        if(j>=(r-l+1)&&l<=l1&&l1<=r1&&r1<=r)
                        {
                            if(f[i-1][j-(r-l+1)][l1][r1][0][0]+sum[i][r]-sum[i][l-1]>f[i][j][l][r][0][0])
                            {
                                 f[i][j][l][r][0][0]=f[i-1][j-(r-l+1)][l1][r1][0][0]+sum[i][r]-sum[i][l-1];
                                 pre[i][j][l][r][0][0]={i-1,j-(r-l+1),l1,r1,0,0};
                            }
                        }
                        if(j>=(r-l+1)&&l1<=l&&r>=l&&r1>=r)
                        {
                            if(f[i-1][j-(r-l+1)][l1][r1][1][1]+sum[i][r]-sum[i][l-1]>f[i][j][l][r][1][1])
                            {
                                 f[i][j][l][r][1][1]=f[i-1][j-(r-l+1)][l1][r1][1][1]+sum[i][r]-sum[i][l-1];
                                 pre[i][j][l][r][1][1]={i-1,j-(r-l+1),l1,r1,1,1};
                            }
                        }
                        if(j>=(r-l+1)&&l1<=l&&r>=l&&r1>=r)
                        {
                            if(f[i-1][j-(r-l+1)][l1][r1][1][0]+sum[i][r]-sum[i][l-1]>f[i][j][l][r][1][1])
                            {
                                 f[i][j][l][r][1][1]=f[i-1][j-(r-l+1)][l1][r1][1][0]+sum[i][r]-sum[i][l-1];
                                 pre[i][j][l][r][1][1]={i-1,j-(r-l+1),l1,r1,1,0};
                            }
                        }
                        if(j>=(r-l+1)&&l1<=l&&l<=r1&&r>=r1)
                        {
                            if(f[i-1][j-(r-l+1)][l1][r1][1][0]+sum[i][r]-sum[i][l-1]>f[i][j][l][r][1][0])
                            {
                                 f[i][j][l][r][1][0]=f[i-1][j-(r-l+1)][l1][r1][1][0]+sum[i][r]-sum[i][l-1];
                                 pre[i][j][l][r][1][0]={i-1,j-(r-l+1),l1,r1,1,0};
                            }
                        }
                        if(j>=(r-l+1)&&l1<=l&&r>=l&&r1>=r)
                        {
                            if(f[i-1][j-(r-l+1)][l1][r1][0][1]+sum[i][r]-sum[i][l-1]>f[i][j][l][r][1][1])
                            {
                                 f[i][j][l][r][1][1]=f[i-1][j-(r-l+1)][l1][r1][0][1]+sum[i][r]-sum[i][l-1];
                                 pre[i][j][l][r][1][1]={i-1,j-(r-l+1),l1,r1,0,1};
                            }
                        }
                        if(j>=(r-l+1)&&l<=l1&&r>=l1&&r1>=r)
                        {
                            if(f[i-1][j-(r-l+1)][l1][r1][0][1]+sum[i][r]-sum[i][l-1]>f[i][j][l][r][0][1])
                            {
                                 f[i][j][l][r][0][1]=f[i-1][j-(r-l+1)][l1][r1][0][1]+sum[i][r]-sum[i][l-1];
                                 pre[i][j][l][r][0][1]={i-1,j-(r-l+1),l1,r1,0,1};
                            }
                        }
                        if(j==k)
                        {
                            for(int il=0;il<2;il++)
                            {
                                for(int jl=0;jl<2;jl++)
                                {
                                    if(f[i][j][l][r][il][jl]>ans)
                                    {
                                        ans=f[i][j][l][r][il][jl];
                                        t={i,j,l,r,il,jl};
                                    }
                                }
                            }
                        }
                       }
                   }
               }
           }
        }
    }
    printf("Oil : %d \n",ans);
    while(k)
    {
        int i=t.aa,j=t.ab,l=t.ac,r=t.ad,k1=t.ae,k2=t.af;
        k-=(r-l+1);
        for(int y=l;y<=r;y++)
        {
            printf("%d %d\n",i,y);
        }
        t=pre[i][j][l][r][k1][k2];
    }
    return 0;
}