hdu 6289 寻宝游戏_小q最近迷上了一款寻宝游戏,这款游戏中每局都会生成一个n\times m的网格地图,从上

寻宝游戏

上为qls题解截图。

下边是我做题中的愚见：

题目一看就是DP，有一种从1,1到n,m的n^2的DP，然而这个多了k次交换，所以题目从2维DP变成了4维DP。

dp[i][j][p][q]:表示走到(i,j)位置必经之路上没拿了p个非必经之路上拿了q个。

状态转移方程：

dp[i][j][p][q] = max ( dp[i][j][p][q] , dp[i-1][j][p][q]+mp[i][j] );//从上边直接下来

dp[i][j][p][q] = max ( dp[i][j][p][q] , dp[i-1][j][p-1][q] );

dp[i][j][p][q] = max ( dp[i][j][p][q] , dp[i][j][p][q-r]+que[r] );

dp[i][j][p][q] = max ( dp[i][j][p][q] , dp[i][j-1][p][q]+mp[i][j] );

dp[i][j][p][q] = max ( dp[i][j][p][q] , dp[i][j-1][p-1][q] );

#include <bits/stdc++.h>
using namespace std;
int Map[55][55];
int dp[55][55][55][55];
int a[55];
int Index;
int cmp(int a,int b)
{
	return a>b;
}
int main() 
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
    	int n,m,k;
    	scanf("%d%d%d",&n,&m,&k);
    	for(int i=1;i<=n;i++)
    		for(int j=1;j<=m;j++)
    			scanf("%d",&Map[i][j]);
    	memset(dp,-1,sizeof(dp));
    	
    	dp[1][1][0][0]=Map[1][1];//取了第一个 
    	dp[1][1][1][0]=0;		//没取 
    	
	for(int i=1;i<=n;i++)//n*n*k*k*k
    	{
            for(int j=1;j<=m;j++)
	   {
			a[0]=0;
			Index=0;		
			for(int k=1;k<=m;k++)//是从当前点往前和上一行当前点往后 
			{
				if(k<j)
					a[++Index]=Map[i][k];
				else if(k>j)
					a[++Index]=Map[i-1][k];
			}
				
			sort(a+1,a+Index+1,cmp); //从大到小排序 将那些不是必经之路上的点取出来
			
			for(int k=1;k<=Index;k++)//求个前缀和
				a[k]=a[k]+a[k-1];
				
			for(int p=0;p<=k;p++)
			{
				for(int q=0;q<=k;q++)
				{
					if(dp[i-1][j][p][q]!=-1) //从上边过来(经过的路上) 
						dp[i][j][p][q]=max(dp[i][j][p][q],dp[i-1][j][p][q]+Map[i][j]); 
					if(p>=1 && dp[i-1][j][p-1][q]!=-1)//考虑有个点取还是没取 比如前边的那个第一个点 
							dp[i][j][p][q]=max(dp[i][j][p][q],dp[i-1][j][p-1][q]); 
				}	
			}	
			for(int p=k;p>=1;p--)
			{
				for(int q=k;q>=0;q--)
				{
					for(int r=p;r>=1;r--)//有多少非必经之路的 
					{
					    if(dp[i][j][q][p-r]!=-1 && p-r>=0)//取出来r个 
							dp[i][j][q][p]=max(dp[i][j][q][p],dp[i][j][q][p-r]+a[r]); 
					}
				}
			}
			for(int p=0;p<=k;p++)
			{
				for(int q=0;q<=k;q++)
				{
					if(dp[i][j-1][p][q]!=-1)
						dp[i][j][p][q]=max(dp[i][j][p][q],dp[i][j-1][p][q]+Map[i][j]); 
					if(p>=1 && dp[i][j-1][p-1][q]!=-1)
						dp[i][j][p][q]=max(dp[i][j][p][q],dp[i][j-1][p-1][q]);
				}
			 } 
		}		
	}
	int ans=0;
	for(int i=0;i<=k;i++)
		ans=max(ans,dp[n][m][i][i]);
	printf("%d\n",ans);
    }
    return 0;
}