一道消磨人的题,自己手画一下状态就好了。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#define gc getchar()
using namespace std;
inline void qr(int &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(int x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
int f[16][226][16][16][2][2],a[16][16],b[16][16];
int pl[16][226][16][16][2][2],pr[16][226][16][16][2][2];
int px[16][226][16][16][2][2],py[16][226][16][16][2][2];
void update(int val,int i,int j,int l,int r,int x,int y,int L,int R,int X,int Y)
{
if(f[i][j][l][r][x][y]>=val)return ;
f[i][j][l][r][x][y]=val;
pl[i][j][l][r][x][y]=L;pr[i][j][l][r][x][y]=R;
px[i][j][l][r][x][y]=X;py[i][j][l][r][x][y]=Y;
}
void pri(int i,int j,int l,int r,int x,int y)
{
if(!j)return ;
pri(i-1,j-(r-l+1),pl[i][j][l][r][x][y],pr[i][j][l][r][x][y],px[i][j][l][r][x][y],py[i][j][l][r][x][y]);
for(int k=l;k<=r;k++)printf("%d %d\n",i,k);
}
int main()
{
int n,m,t;qr(n),qr(m),qr(t);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
qr(a[i][j]);
b[i][j]=b[i][j-1]+a[i][j];
}
memset(f,0xcf,sizeof(f));
for(int i=1;i<=n;i++)
for(int j=1;j<=t;j++)
for(int l=1;l<=m;l++)
for(int r=l;r<=m;r++)
{
int k=r-l+1;if(k>j)break;
int now=b[i][r]-b[i][l-1];
if(k==j)
for(int x=0;x<2;x++)
for(int y=0;y<2;y++)
update(now,i,j,l,r,x,y,m,0,x,y);
else
{
for(int p=l;p<=r;p++)
for(int q=p;q<=r;q++)
update(f[i-1][j-k][p][q][1][0]+now,i,j,l,r,1,0,p,q,1,0);//1表示递减,0表示递增
for(int p=l;p<=r;p++)
for(int q=r;q<=m;q++)
for(int y=0;y<2;y++)
update(f[i-1][j-k][p][q][1][y]+now,i,j,l,r,1,1,p,q,1,y);
for(int p=1;p<=l;p++)
for(int q=l;q<=r;q++)
for(int x=0;x<2;x++)
update(f[i-1][j-k][p][q][x][0]+now,i,j,l,r,0,0,p,q,x,0);
for(int p=1;p<=l;p++)
for(int q=r;q<=m;q++)
for(int x=0;x<2;x++)
for(int y=0;y<2;y++)
update(f[i-1][j-k][p][q][x][y]+now,i,j,l,r,0,1,p,q,x,y);
}
}
int ans=0,ansi,ansl,ansr,ansx,ansy;
for(int i=1;i<=n;i++)
for(int l=1;l<=m;l++)
for(int r=l;r<=m;r++)
for(int x=0;x<2;x++)
for(int y=0;y<2;y++)
if(ans<f[i][t][l][r][x][y])
{
ans=f[i][t][l][r][x][y];
ansi=i,ansl=l,ansr=r,ansx=x,ansy=y;
}
printf("Oil : %d\n", ans);
pri(ansi,t,ansl,ansr,ansx,ansy);
return 0;
}
最后一次更新于2019-10-17
0 条评论