问题解释：n行，每行挑选都从m列中选走一个值，且每行挑选的列需要在上一行挑选的列的后面，并记录每行选取的位置 解：令f[i][j]表示选完 i 行且第 i 行选的值是a[i][j]的最大值 则有：f[i][j]=max(f[i][k]+a[i][j])，(1<=k<j) 并且令pre[i][j]记录其 i-1选取的列
#include<bits/stdc++.h> using namespace std; int n,m,a[105][105],f[105][105],pre[105][105]; stack<int> stk; int main() { cin>>n>>m; for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { cin>>a[i][j]; } } for(int i=1; i<=m-n; i++) { f[1][i]=a[1][i]; pre[1][i]=i; //对第一行先进行处理 } for(int i=2; i<=n; i++) { for(int j=i; j<=m-n+i; j++) { //注意i<=j<=m-n+i for(int k=1; k<j; k++) { //枚举上一行中最大的dp值 if(f[i-1][k]+a[i][j]>f[i][j]) { f[i][j]=f[i-1][k]+a[i][j]; pre[i][j]=k; } } } } int ans=-1e9,t; for(int j=n;j<=m;j++){ if(f[n][j]>ans){ ans=f[n][j]; t=j; } } cout<<ans<<endl; for(int i=n;i>=1;i--){ stk.push(t); t=pre[i][t]; } while(!stk.empty()){ cout<<stk.top()<<" "; stk.pop(); } return 0; }有一个很好想的思路，就是从每个x=1的点出发，做dfs，求出其所能到达的 l，r，以及判断 [l,r] 区间内的每个点是否可达即可 如果不满足条件：则一定有点未达到，判断一下vis即可 如果满足条件：我们用求出的所有 [l,r] 做线段覆盖即可 朴素的复杂度是O（m2 n)，有点超时 如何进行优化？ 记忆化搜索！！！ 用数组存储每个点能到达的最左边和最右边的干旱区，每个点只经过一次，回溯的时候更新一下每个点能够到达的左右点即可
#include<bits/stdc++.h> using namespace std; const int N=502; int n,m; int l[N][N],r[N][N],vis[N][N],a[N][N],cnt; int xx[4]={0,0,-1,1}; int yy[4]={-1,1,0,0}; void dfs(int x,int y){ if(x==n){ l[x][y]=min(l[x][y],y); r[x][y]=max(r[x][y],y); } vis[x][y]=1; for(int i=0;i<4;i++){ int tx=x+xx[i]; int ty=y+yy[i]; if(tx>=1&&tx<=n&&ty>=1&&ty<=m){ if(a[tx][ty]<a[x][y]){ if(!vis[tx][ty])dfs(tx,ty); l[x][y]=min(l[x][y],l[tx][ty]); r[x][y]=max(r[x][y],r[tx][ty]); } } } } int check(){ for(int j=1;j<=m;j++){ if(vis[n][j]==0)cnt++; } if(cnt)return 1; else return 0; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; l[i][j]=1000; r[i][j]=-1000; } } for(int j=1;j<=m;j++){ if(!vis[1][j])dfs(1,j); } if(check()){ cout<<0<<endl<<cnt; return 0; } int now=1,maxj; cnt=0; while(now<=m){ maxj=0; for(int j=1;j<=m;j++){ if(l[1][j]>r[1][j])continue; if(l[1][j]<=now){ maxj=max(maxj,r[1][j]); } } cnt++; now=maxj+1; } cout<<1<<endl<<cnt; return 0; }