洛谷P2258 子矩阵

Topic Links

Topic meaning:在n行m列中找出一个r行c列的子矩阵，求此子矩阵最小的分值

Topic of solving:动态规划

枚举r行的全排列情况，对每一种情况运用动态规划求出其m列中选取c列算得的最小分值

设f[i][j]为前i列中选j列可得的最小分值，f[i][j]已选中第i列

则f[i][j]=min(f[i][j],f[k][j-1]+up[j]+hc[k][j]);j-1<=k

边界情况：

j=1即前i列选1列则只能是选中第i列

i=j即前i列均被选中

#include
#include
using namespace std;
int n,m,r,l,a[20][20],up[20],hc[20][20],dp[20][20];
int r_x[20],v_r[20],ans=10000000;
void choose(int amount,int now_r){
if(amount==r) {
for(int i=1;i<=m;i++){
up[i]=0;
for(int j=1;j>n>>m>>r>>l;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) cin>>a[i][j];
        for(int i=1;i<=n;i++){
        if(!v_r[i]){
        v_r[i]=1;r_x[1]=i;
        choose(1,i);
        v_r[i]=0;
        }
        }
        cout<