Algospot - QUANTIZE 알고리즘

//

//  main.cpp

//  quatnization

//

//  Created by sungjuho on 2014. 4. 20..

//  Copyright (c) 2014 sungjuho. All rights reserved.

//

#include <cstdio>

#include <cstring>

#include <algorithm>


#define N 101

#define MAX 1000000000


using namespace std;


int nCase,patternLen,useNum;

int input[N];

int dp[N][10];


inline int roundToInt(float val){return (int)(val+0.5);}


inline int getQuant(int s, int len)

{

    int result=0;

    int avgSum=0;

    int avg ;

    int d;

    

    for(int i=0; i < len; ++i)

    {

        avgSum += input[s+i];

    }

    

    avg = roundToInt( (float)((float)avgSum / len));

    

    for(int i=0; i < len; ++i)

    {

        d = input[s+i]-avg;

        result += d*d;

    }

    

    return result;

    

}

int solve(int s, int n, int k)

{

    if(patternLen<=useNum)

        return 0;

    

    if(dp[n][k])

    {

        return dp[n][k];

    }

    

    if(k==1)

    {

        return getQuant(s, patternLen-s);

    }

   

    int sum = 0;

    int min = MAX;

    

    for(int i=1; i <= n-k+1; ++i)

    {

        sum = getQuant(s, i);


        sum += solve(s+i, n-i, k-1);

        

        if(sum < min )

        {

            min = sum;

        }

    }

    

    dp[n][k] = min;

    

    return dp[n][k];

    

}


int main(int argc, const char * argv[])

{

    scanf("%d",&nCase);

    

    while(nCase-->0)

    {

        scanf("%d%d",&patternLen,&useNum);

        

        memset(dp, 0, sizeof(int)*N*10);

        

        for(int i=0; i < patternLen; ++i)

        {

            scanf("%d",&input[i]);

        }


        sort(input, input+patternLen);

        

        printf("%d\n",solve(0,patternLen, useNum));

    }

    return 0;

}



덧글

댓글 입력 영역