matrix 矩阵（多维DP）-白红宇

matrix 矩阵（多维DP）

阅读量：4610 次

发布时间：2019-06-09

本文共 1286 字，大约阅读时间需要 4 分钟。

题面

\(solution:\)

这一题其实就是一个非常明显的三维背包问题（但博主太弱了就10分QAQ）

\(F[i][j][k]:\)表示走到\((i,j)\)这个位置并且背包容量为 \(k\) 时的最大价值。因为转移时只能向下或向右转移，所以我们可以按行\(DP\)（从上到下，从左到右遍历），进行滚动数组，从而把第一位省去。

\(code:\)

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #define ll long long#define db double#define inf 0x7fffffff#define rg register intusing namespace std;int n,m,t,ans;int a[405][405];int b[405][405];int f[405][405];inline int qr(){ char ch; while((ch=getchar())<'0'||ch>'9'); int res=ch^48; while((ch=getchar())>='0'&&ch<='9') res=res*10+(ch^48); return res;}int main(){ //freopen("matrix.in","r",stdin); //freopen("matrix.out","w",stdout); n=qr(),m=qr(),t=qr(); for(rg i=1;i<=n;++i) for(rg j=1;j<=m;++j) a[i][j]=qr(); for(rg i=1;i<=n;++i) for(rg j=1;j<=m;++j) b[i][j]=qr(); for(rg i=1;i<=n;++i){ for(rg j=1;j<=m;++j){ for(rg k=0;k<=t;++k){ f[j][k]=max(f[j][k],f[j-1][k]); if(k+a[i][j]>t)continue; f[j][k]=max(f[j][k],f[j][k+a[i][j]]+b[i][j]); f[j][k]=max(f[j][k],f[j-1][k+a[i][j]]+b[i][j]); } } } for(rg j=1;j<=m;++j) for(rg i=0;i<=t;++i) ans=max(ans,f[j][i]); printf("%d\n",ans); return 0;}

转载于:https://www.cnblogs.com/812-xiao-wen/p/10328324.html

你可能感兴趣的文章