2013年9月29日 星期日

2013/9/29 STEP5 0042 : Ch4-2.賭上肥皂的對決 (有時AC有時TLE="=)

// http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0042
#include <iostream>
#include <cstdio>

using namespace std;

long long int DP[5001][1001]; int C[5001];

int main()
{
    int T;
    scanf("%d", &T);

    while( T-- )
    {
        int K, N;
        scanf("%d %d", &K, &N);

        for(int i = N; i >= 1; i--)
            scanf("%d", &C[i]);

        long long int INF = (long long int)(1)<<60;

        for(int i = 0; i <= N; i++)
            for(int j = 1; j <= K; j++)
                DP[i][j] = INF;

        for(int i = 1; i <= N; i++)
        {
            long long int t = (C[i]-C[i-1]); t*=t;
            for(int j = 1; j <= K; j++)
            {
                if( j*3 <= i )
                    DP[i][j] = min( DP[i-1][j], DP[i-2][j-1]+t);
                else
                    break;
            }



        }

        printf("%lld\n", DP[N][K]);
    }
}

沒有留言:

張貼留言