Description

Input

Output

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

Data Constraint

Hint

Solution

• 看到這樣分層的最優(yōu)值問題，毫無疑問就是DP了。

• 考慮把“豆豆”和“ 磚塊”一起DP，方便處理。

• 設(shè) F[i][j][k] 表示做到前 i 行、蛇的長度還剩下 j 、從第 k 列轉(zhuǎn)移出去的最大得分。

• 設(shè) G[j][l][r] 表示蛇的長度還剩下 j ，當前行在第 l 列和第 r 列來回移動仍未死亡的最大得分。

• 顯然，初始狀態(tài)為：F[0][4][3]=0

• 對于每一個 i ，首先令：G[j][k][k]=G[j?a[i][k]][k][k]+Max(?a[i][k],0)

• 接著再往兩邊擴展（即從 l 或 r 轉(zhuǎn)移過來， 注意若有隔板則不能轉(zhuǎn)移）：

  G[j][l][r]=Max{G[j?a[i][l]][l+1][r]+Max(?a[i][l],0),G[j?a[i][r]][l][r?1]+Max(?a[i][r],0)}

• 最后：

  F[i][j][k]=Max{G[j][l][r]}(1≤l≤k≤r≤5)

• 則取最大值即可：

  ans=Max{F[i][j][k]}

• 這樣的時間復(fù)雜度為 O(N?(5?Max{A[i][j]}?N)) 。

Code

#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() {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;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];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; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 5393. 【NOIP2017提高A组模拟10.5】Snake vs Block的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。