Sample Input
5
-2 0 0 1 -2
0 2 0 0 0
-4 -3 -2 -3 -7
1 0 0 0 0
0 -2 0 -2 0
0
Sample Output
8
题解
这是一道比较困难的DP,因为它分层，所以很容易想到DP，具体实现参考代码：
#include<cstdio>
#include<cstring>
using namespace std;
const int N=201,M=10001;
int ans,roll;
int a[N][5],b[N][5],f[2][M][5],g[M][5][5];
bool bz[N][5];
inline int read()
{
int X=0,w=1; char ch=0;
while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
return X*w;
}
inline int max(int x,int y)
{
return x>y?x:y;
}
int main()
{
freopen("snakevsblock.in","r",stdin);
freopen("snakevsblock.out","w",stdout);
int n=read(),mx=n*50;
for(int i=1;i<=n;i++)
for(int j=0;j<5;j++)
{
a[i][j]=read();
b[i][j]=max(-a[i][j],0);//得分
}
int m=read();
while(m--)
{
int x=read(),y=read();
bz[x][y-1]=true;//墙壁
}
memset(f,128,sizeof(f));
f[0][4][2]=0;//dp
for(int i=1;i<=n;i++)
{
roll^=1;
memset(f[roll],128,sizeof(f[roll]));
memset(g,128,sizeof(g));
for(int j=0;j<=mx;j++)//长度(现在)
for(int k=0;k<5;k++)//纵列
{
int s=j-a[i][k];//表示曾经的长度
if(s>=0 && s<=mx) f[roll][j][k]=g[j][k][k]=f[roll^1][s][k]+b[i][k];//这里可以走
}
for(int k=1;k<5;k++)//区间长
for(int l=0;l+k<5;l++)//左端点
for(int j=0;j<=mx;j++)//长度
{
int r=l+k,s=j-a[i][l];//计算右端点和曾经的长度
if(!bz[i][l] && s>=0 && s<=mx) g[j][l][r]=g[s][l+1][r]+b[i][l];//从(l,r]区间变成[l,r]
s=j-a[i][r];
if(!bz[i][r-1] && s>=0 && s<=mx) g[j][l][r]=max(g[j][l][r],g[s][l][r-1]+b[i][r]);//同上
for(int p=l;p<=r;p++) f[roll][j][p]=max(f[roll][j][p],g[j][l][r]);//更新
}
for(int j=0;j<=mx;j++)
for(int k=0;k<5;k++) ans=max(ans,f[roll][j][k]);//算答案
}
printf("%d",ans);
return 0;
}
/*
因为如果算i的话,只能从上面下来,所以可以用滚动数组优化空间.
*/
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string.h>
using namespace std;
const int maxn=210;
int a[maxn][6],b[maxn][6],bz[maxn][6];
int f[2][10010][6],g[10010][6][6];
int main(){
// freopen("snakevsblock.in","r",stdin);
// freopen("snakevsblock.out","w",stdout);
int i,j,k,n,m,ans=0;
scanf("%d",&n);
int lm=n*50;
for(i=1;i<=n;i++)
for(j=0;j<5;j++){
scanf("%d",&a[i][j]);
b[i][j]=max(0,-a[i][j]);
}
scanf("%d",&m);
for(i=1;i<=m;i++){
int x,y;scanf("%d%d",&x,&y);
bz[x][y-1]=1;
}
memset(f,-128,sizeof(f));
f[0][4][2]=0;
int gd=0;
for(i=1;i<=n;i++){
gd^=1;
memset(f[gd],-128,sizeof(f[gd]));
memset(g,-128,sizeof(g));
for(j=0;j<=lm;j++)
for(k=0;k<5;k++){
int sold=j-a[i][k];
if(sold>=0 && sold<=lm)f[gd][j][k]=g[j][k][k]=f[gd^1][sold][k]+b[i][k];
}
for(k=1;k<5;k++)
for(int l=0;l+k<5;l++)
for(j=0;j<=lm;j++){
int r=l+k,sold=j-a[i][l];
if(!bz[i][l] && sold>=0 && sold<=lm)
g[j][l][r]=g[sold][l+1][r]+b[i][l];
sold=j-a[i][r];
if(!bz[i][r-1] && sold>=0 && sold<=lm)
g[j][l][r]=max(g[j][l][r],g[sold][l][r-1]+b[i][r]);
for(int p=l;p<=r;p++)
f[gd][j][p]=max(f[gd][j][p],g[j][l][r]);
}
for(j=0;j<=lm;j++)
for(k=0;k<5;k++)
ans=max(ans,f[gd][j][k]);
}
printf("%d
",ans);
return 0;
}