[NOIP2014] [vijos1914] 하위 행렬(dp)

코드

#include
#include
#include
using namespace std;

int n,m,r,c,inf,ans;
int a[20][20],sol[15000],f[20][20][15000],dif[20][15000],diff[20][20][15000];

int Abs(int x)
{
    return (x>0)?x:-x;
}
int calc(int x)
{
    int ans=0;
    while (x)
    {
        ans+=(x&1);
        x>>=1;
    }
    return ans;
}
int _calc(int id,int x)
{
    int ans=0,dig[20];dig[0]=0;
    for (int i=0;iif ((x>>i)&1) dig[++dig[0]]=m-i;
    for (int i=dig[0];i>1;--i)
        ans+=Abs(a[id][dig[i]]-a[id][dig[i-1]]);
    return ans;
}
int __calc(int id,int jd,int x)
{
    int ans=0;
    for (int i=0;iif ((x>>i)&1) ans+=Abs(a[id][m-i]-a[jd][m-i]);
    return ans;
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&r,&c);
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j) scanf("%d",&a[i][j]);
    for (int i=0;i<=(1<1;++i)
        if (calc(i)==c) sol[++sol[0]]=i;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=sol[0];++j)
            dif[i][j]=_calc(i,sol[j]);
    for (int i=1;i<=n;++i)
        for (int j=i+1;j<=n;++j)
            for (int k=1;k<=sol[0];++k)
                diff[i][j][k]=__calc(i,j,sol[k]);
    memset(f,127,sizeof(f));inf=f[0][0][0];
    for (int i=1;i<=n;++i)
        for (int j=1;j<=sol[0];++j)
            f[i][0][j]=0,f[i][1][j]=dif[i][j];
    for (int i=2;i<=n;++i)
        for (int j=1;j<=min(i,r);++j)
            for (int k=1;k<=sol[0];++k)
                for (int l=1;lif (f[l][j-1][k]!=inf)
                        f[i][j][k]=min(f[i][j][k],f[l][j-1][k]+diff[l][i][k]+dif[i][k]);
    ans=inf;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=sol[0];++j)
            ans=min(ans,f[i][r][j]);
    printf("%d
",ans);
}

총결산