BZOJ_5359_[Lydsy1805月赛]寻宝游戏_DP

BZOJ5359_[Lydsy1805月赛]寻宝游戏_DP

Description

begin.lydsy.com/JudgeOnline/upload/201805.pdf

---

我们需要找到一条权值最大的路，其中路上可以有K个点不计入答案，同时使不在路径上的K个点被计入答案。

设f[i][j][k][l]表示从(1,1)走到(i,j)路径上k个不算答案，路径外计入了l个。

转移的话先是考虑下一步走的点取不取，然后对应着一行/一列取多少个。

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cstdlib>

using namespace std;

typedef long long ll;

#define N 55

int n,m,K,a[N][N];

int g[N][N][N],h[N][N][N],f[N][N][21][21],lb,b[N];

void upd(int &x,int y) {

	if(x<y) x=y;

}

void solve() {

	scanf("%d%d%d",&n,&m,&K);

	int i,j,k,l,d;

	for(i=1;i<=n;i++) {

		for(j=1;j<=m;j++) {

			scanf("%d",&a[i][j]);

		}

	}

	memset(g,0,sizeof(g)); memset(h,0,sizeof(h));

	for(i=1;i<=n;i++) {

		for(j=1;j<=m;j++) {

			lb=0;

			for(k=j+1;k<=m;k++) b[++lb]=-a[i][k];

			sort(b+1,b+lb+1);

			for(k=1;k<=lb;k++) g[i][j][k]=g[i][j][k-1]-b[k];

			lb=0;

			for(k=i+1;k<=n;k++) b[++lb]=-a[k][j];

			sort(b+1,b+lb+1);

			for(k=1;k<=lb;k++) h[i][j][k]=h[i][j][k-1]-b[k];

		}

	}

	// for(i=1;i<=n;i++) {

	// 	for(j=1;j<=m;j++) {

	// 		printf("%d %d\n",g[i][j][1],g[i][j][2]);

	// 	}

	// }

	memset(f,0x80,sizeof(f));

	f[1][1][1][0]=0;

	f[1][1][0][0]=a[1][1];

	for(i=1;i<=n;i++) {

		for(j=1;j<=m;j++) {

			for(k=0;k<=K;k++) {

				for(l=0;l<=K;l++) {

					for(d=0;d<=K-l&&d<=m-j;d++) {

						upd(f[i+1][j][k][l+d],f[i][j][k][l]+g[i][j][d]+a[i+1][j]);

						upd(f[i+1][j][k+1][l+d],f[i][j][k][l]+g[i][j][d]);

					}

					for(d=0;d<=K-l&&d<=n-i;d++) {

						upd(f[i][j+1][k][l+d],f[i][j][k][l]+h[i][j][d]+a[i][j+1]);

						upd(f[i][j+1][k+1][l+d],f[i][j][k][l]+h[i][j][d]);

					}

				}

			}

		}

	}

	int ans=0;

	for(i=0;i<=K;i++) ans=max(ans,f[n][m][i][i]);

	printf("%d\n",ans);

}

int main() {

	// freopen("game.in","r",stdin);

	// freopen("game.out","w",stdout);

	int T;

	scanf("%d",&T);

	while(T--) solve();

}