这题的转移很明显。
用dp[i][j] 表示到达i层j位置时的最大得分
sum[i][j] 表示第i层前j个数的和
dp[i][j] = max(max(dp[i - 1][j + k] + sum[i-1][j +k-1] - sum[i - 1][j - 1] + score[i][j]), max(dp[i - 1][j - k] - sum[i-1][j -k] + sum[i - 1][j] + score[i][j]))
因为只能移动t步，则就是在t长的窗口中的最小值
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<cstdlib> using namespace std; const int inf=0x3f3f3f3f; inline int read() { int x; scanf("%d",&x); return x; } int n,m,x,t; int sco[105][10005],sum[105][10005],f[105][10005]; int q[10005],id[10005],head,tail; void work() { m=read();x=read();t=read(); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) sco[i][j]=read(),sum[i][j]=sum[i][j-1]+sco[i][j]; for (int i=1;i<=m;i++) if (i!=x) f[1][i]=-inf;else f[1][i]=sco[1][i]; for (int i=2;i<=n+1;i++) { memset(q,0,sizeof(q)); memset(id,0,sizeof(id)); head=1;tail=1; q[1]=f[i-1][1]-sum[i-1][1]; id[1]=1;//注意初始化，不要忘了id【1】之类的 for (int j=1;j<=m;j++) { f[i][j]=-inf; while (head<=tail && id[head]<j-t) head++; f[i][j]=max(f[i][j],q[head]+sco[i][j]+sum[i-1][j]); while (head<=tail && q[tail]<=f[i-1][j+1]-sum[i-1][j+1]) tail--; q[++tail]=f[i-1][j+1]-sum[i-1][j+1]; id[tail]=j+1; } /***********************************************/ memset(q,0,sizeof(q)); memset(id,0,sizeof(id)); head=1;tail=1; q[1]=f[i-1][m]+sum[i-1][m-1]; id[1]=m; for (int j=m;j>=1;j--) { while (head<=tail && id[head]>j+t) head++; f[i][j]=max(f[i][j],q[head]+sco[i][j]-sum[i-1][j-1]); while (head<=tail && q[tail]<=f[i-1][j-1]+sum[i-1][j-2]) tail--; q[++tail]=f[i-1][j-1]+sum[i-1][j-2]; id[tail]=j-1; } } int ans=-inf; for (int i=1;i<=m;i++) ans=max(ans,f[n+1][i]); printf("%d\n",ans); } void clear() { memset(sum,0,sizeof(sum)); memset(sco,0,sizeof(sco)); memset(f,0,sizeof(f)); } int main() { while (scanf("%d",&n)!=EOF) { clear(); work(); } return 0; }
