n×m的矩阵，每个点上有个数字，从左上走到右下，有k次机会可以将两个地方的数字交换，求可取得的最大值。

题解

这是一道dp题，非常的巧妙。先划分状态,f[i][j][k][l]，表示从(1,1)出发来到(i,j)，考虑完前i-1行所有格子及第i行前j个格子时，k个经过的格子不计分，l个经过的格子计分情况下的最大值。
每一个点都向(i,j+1)和(i+1,j)转移状态，注意边界处理和初始化。

#include<bits/stdc++.h>

using namespace std;

int f[51][51][23][23],px[250];
int n,m,k;
int d[51][51];

bool cmp(int a,int b){return a>b;}

int main(){
     int t;
     cin>>t;
     while(t--){
          memset(f,128,sizeof f);
          cin>>n>>m>>k;
          for(int i=1;i<=n;++i)
               for(int j=1;j<=m;++j) scanf("%d",&d[i][j]);
          f[1][1][0][0]=d[1][1];
          f[1][1][1][0]=0;
          for(int i=1;i<=n;++i)
               for(int j=1;j<=m;++j){
                    if(i-n){
                         int jis=0;
                         memset(px,0,sizeof px);
                         for(int ii=j+1;ii<=m;++ii) px[++jis]=d[i][ii];
                         for(int ii=1;ii<j;++ii) px[++jis]=d[i+1][ii];
                         sort(px+1,px+jis+1,cmp);
                         for(int ii=1;ii<=jis;++ii) px[ii]+=px[ii-1];
                         for(int ii=0;ii<=k;++ii)
                                   for(int jj=0;jj<=k;++jj)
                                for(int h=0;h<=jis&&h<=jj;++h){
                                    f[i+1][j][ii][jj]=max(f[i+1][j][ii][jj],d[i+1][j]+f[i][j][ii][h]+px[jj-h]);
                                    f[i+1][j][ii+1][jj]=max(f[i+1][j][ii+1][jj],f[i][j][ii][h]+px[jj-h]);
                                }
                    }
                    if(j-m){
                         for(int ii=0;ii<=k;++ii)
                              for(int jj=0;jj<=k;++jj){
                                   f[i][j+1][ii][jj]=max(f[i][j][ii][jj]+d[i][j+1],f[i][j+1][ii][jj]);
                                   f[i][j+1][ii+1][jj]=max(f[i][j+1][ii+1][jj],f[i][j][ii][jj]);
                              }
                    }
               }
          int ans=0;
          for(int i=0;i<=k;++i) ans=max(ans,f[n][m][i][i]);
          cout<<ans<<endl;
     }
     return 0;
}

感想

这个傻逼边界处理调了我一个小时。刚开始是赋成0，没有考虑各自为0的情况，之后赋值成了-1，但是也会被奇怪的数据卡掉。改成了-INF才过。果然hdu的题还是毒瘤。

优质内容筛选与推荐>>
1、第三方邮件客户端收取163邮件问题（收邮件NO Select Unsafe Login. Please contact kefu解决办法）
2、爬虫—天眼查接口函数
3、dom4j解析xml配置文件
4、编译参数中-pthread以及-lpthread的区别
5、课11

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。

阅读

已发送

发送中