sgu 205

  • Post author:
  • Post category:其他











D


p











j


u


s


t




m


a


k


e




s


e


n


s


e


.










时间复杂度:








O


(


n








s






2







)











#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>

const int MAXN = 1e3+5, SZ = (1<<7)+1, INF = 0x3f3f3f3f;

int n, x[MAXN], m, s, A[SZ][SZ];
int f[MAXN][SZ], g[MAXN][SZ];
int ans = INF, des;

void Init()
{
    scanf("%d",&n);
    for(int i = 1; i <= n; i++)
        scanf("%d",&x[i]);

    scanf("%d%d",&m,&s);
    for(int i = 0; i < m; i++)
        for(int j = 0; j < s; j++)
            scanf("%d",&A[i][j]);
}
void Solve()
{
    memset(f,INF,sizeof(f)), f[0][0] = 0;

    for(int i = 1; i <= n; i++)
        for(int j = 0; j < s; j++)
            for(int k = 0; k < s; k++)
            {
                int cal = f[i-1][k] + abs(A[k%m][j]-x[i]);
                if(cal < f[i][j]) f[i][j] = cal, g[i][j] = k;
            }   
    for(int j = 0; j < s; j++)
        if(f[n][j] < ans) ans = f[n][j], des = j;       
    printf("%d\n",ans); 
}
void Prt(int pos,int des)
{
    if(!pos) return;

    Prt(pos-1,g[pos][des]);

    printf("%d ",des);
}


int main()
{
#ifndef ONLINE_JUDGE
    freopen("sgu205.in","r",stdin);
    freopen("sgu205.out","w",stdout);
#endif

    Init();     

    Solve();

    Prt(n, des);

#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
#endif
    return 0;               
}



版权声明:本文为cyxhahaha原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。