話不多說，直接看題：

目錄

1.雙線程DP

2.正難則反+多組DP

3.換個方向思考：

---

1.雙線程DP

可能有人會說直接貪心：先選第1條的最優路徑，再選第2條最優路徑。

其實我們再選第1條時，我們怎么選會對第2條的路徑產生影響，不滿足無后效性。

我們選另一種思路：我們可以把問題看作A同時向B傳2張紙條，我們令f[i][j][m][n]表示一張紙條在（i,j),另一個在(m,n)時的最優值，這樣就滿足了無后效性。

易得轉移方程：

f[i][j][m][n]=a[i][j]+a[m][n]+max(f[i-1][j][m-1][n],f[i-1][j][m][n-1],f[i][j-1][m-1][n],f[i][j-1][m][n-1]).

同時，我們令f[i][j][i][j]為負無窮即可。

下面是AC代碼：

#include<bits/stdc++.h>
using namespace std;
int m,n,a[60][60],dp[52][52][52][52];
int f(int i,int j,int x,int y){if(dp[i][j][x][y]!=-1){return dp[i][j][x][y];}if(i==x&&j==y) return dp[i][j][x][y]=-10000000;if(i-1>=1&&x-1>=1) dp[i][j][x][y]=max(dp[i][j][x][y],f(i-1,j,x-1,y));if(i-1>=1&&y-1>=1) dp[i][j][x][y]=max(dp[i][j][x][y],f(i-1,j,x,y-1));if(j-1>=1&&x-1>=1) dp[i][j][x][y]=max(dp[i][j][x][y],f(i,j-1,x-1,y));if(j-1>=1&&y-1>=1) dp[i][j][x][y]=max(dp[i][j][x][y],f(i,j-1,x,y-1));dp[i][j][x][y]+=a[i][j]+a[x][y];return dp[i][j][x][y];
}
int main(){cin>>m>>n;memset(dp,-1,sizeof(dp));dp[1][1][1][1]=0;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){cin>>a[i][j];}}cout<<f(m-1,n,m,n-1);
}

接題：

2.正難則反+多組DP

我們自然地想到用g[i][j]表示第i件物品不能帶，背包大小為j的方案數。

直接求無從下手，我們考慮他其實就是背包大小為j的方案數-g[i][j-v[i]].

下面是AC代碼：

#include<bits/stdc++.h>
using namespace std;
#define mod 10
int n,m,f[2350][2350],g[2350][2350],k[2350];
int main(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>k[i];f[0][0]=1;for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){if(j<k[i]) f[i][j]=f[i-1][j]%mod;else{f[i][j]=(f[i-1][j]%mod+f[i-1][j-k[i]]%mod)%mod;}}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(j<k[i]) g[i][j]=f[n][j];else if(j==k[i])   g[i][j]=(f[n][j]-1+mod)%mod;else g[i][j]=(f[n][j]%mod-g[i][j-k[i]]%mod+mod)%mod;cout<<g[i][j]%mod;}cout<<endl;}
}

接題：

3.換個方向思考：

如果我們一行一行看，不像互不侵犯可以枚舉，于是我們換個角度，我們斜著看，即：

我們發現，在斜著的一列，要敲某一個則必須把他斜上方的都敲了，因此，我們一定是敲的靠上的斜著的某一段。

同時他靠右的一斜列至少要敲到他的層數-1.這樣子就合法了。

我們令f[i][j][k]表示前i列共敲了j塊，第i列敲了k塊。

易得轉移方程：

f[i][j][k]=max(f[i-1][j-k][0--(k+1)]+sum[i][k]]).

下面是AC代碼：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[60][60],sum[60][60],dp[55][510][55];
int main(){cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=n-i+1;j++){cin>>a[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=n-i+1;j++){sum[i][j]=sum[i-1][j]+a[i][j];}}int ans=0;memset(dp,-0x3f,sizeof(dp));dp[n][0][0]=0;dp[n][1][1]=a[1][n];for(int i=n-1;i>=1;i--){for(int j=0;j<=m;j++){for(int k=0;k<=min(n-i+1,j);k++){for(int w=max(k-1,0);w<=n-i;w++){dp[i][j][k]=max(sum[k][i]+dp[i+1][j-k][w],dp[i][j][k]);ans=max(ans,dp[i][j][k]);}}}}cout<<ans;
}