1812. [NOIP2014]子矩阵

http://www.cogs.pro/cogs/problem/problem.php?pid=1812

★★★ 输入文件：submatrix.in 输出文件：submatrix.out 简单对比
时间限制：1 s 内存限制：256 MB

【题目描述】

最暴力的算法是枚举选择哪些行、列。复杂度为O(C(n,r)*C(m,c))。不过显然不能承受。（C为组合数）

注意到虽然O(C(n,r)*C(m,c))不能承受，但O(C(n,r))或O(C(m,c))是可以接受的。

不妨考虑枚举其中一个（假设枚举行）。

枚举完行后，由于行已确定，因此可以把所有行捆绑，视为一个整体。

处理处列与列之间的价值，然后可以用动态规划解决这个问题。

设dp[i][k]表示前i列选了k列，并且第i列强制被选。那么转移方程为：dp[i][k]=dp[j][k-1]+cost[j][i]+val[i]，其中j<i，cost[j][i]表示第i列与第j列相邻的花费，val[i]表示第i列内的花费。

答案即为min{dp[i][c]}。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

using namespace std;

int a[][],m,n,r,c,lr[],ud[],dp[][];

int rlc[],udc[][],ans=0x7fffffff;

void Dp(){

    memset(rlc,,sizeof(rlc));

    memset(udc,,sizeof(udc));

    memset(dp,/,sizeof(dp));

    //不同列之间的差

    for(int i=;i<=m;i++)

        for(int j=;j<i;j++)

            for(int k=;k<=r;k++)

                udc[j][i]+=abs(a[lr[k]][i]-a[lr[k]][j]);

    //不同行之间的差

    for(int i=;i<=m;i++)

        for(int j=;j<r;j++)

            rlc[i]+=abs(a[lr[j]][i]-a[lr[j+]][i]);

    for(int i=;i<=n;i++)dp[i][]=,dp[i][]=rlc[i];

    for(int i=;i<=c;i++){

        for(int j=i;j<=m;j++){

            for(int k=i-;k<j;k++){

                dp[j][i]=min(dp[k][i-]+udc[k][j]+rlc[j],dp[j][i]);

            }

        }

    }

    for(int i=c;i<=m;i++)ans=min(ans,dp[i][c]);

}

void dfs(int Step,int rest){

    if(Step==r){Dp();return;}

    if(r-Step>rest)return;

    for(int i=rest;i>=;i--){lr[Step+]=i;dfs(Step+,i-);}

}

int main(){

    freopen("submatrix.in","r",stdin);

    freopen("submatrix.out","w",stdout);

    scanf("%d%d%d%d",&n,&m,&r,&c);

    for(int i=;i<=n;i++)for(int j=;j<=m;j++)scanf("%d",&a[i][j]);

    dfs(,n);

    printf("%d",ans);

}

巴特西

[NOIP2014]子矩阵

1812. [NOIP2014]子矩阵

【题目描述】

最新文章

热门文章