UVALive6434_Number Assignment

简单dp题。

这样的，意思为给你n个数，要你现在将这n个数分为m组，使得所有组内最大值与最小值的差的和最小。

其实可以这样来考虑这个问题，首先可以把所有的数字从小到大排个序，显然如果有一种取法是最优的，那么所有的组里面的数一定是从小到大排序后中间的一段。

那么这样就可以dp了，f[i][j]表示前i个数分为j组，最小需要花费的代价，这样对于i+1，我们只要直接枚举最后一位数的切断的位置即可。

时间复杂度：O(N^3)

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#define maxn 105

using namespace std;

int n,m,a[maxn],f[maxn][maxn],t,cas=;

int main()

{

    scanf("%d",&t);

    while (t--)

    {

        memset(a,,sizeof a);

        memset(f,0x3f,sizeof f);

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

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

        sort(a+,a++n);

        for (int i=; i<=n; i++) f[i][]=a[i]-a[];

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

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

            {

                for (int k=; k<=j && k<m; k++)

                    f[i][k+]=min(f[i][k+],f[j][k]+a[i]-a[j+]);

            }

        printf("Case #%d: %d\n",++cas,f[n][m]);

    }

    return ;

}

巴特西

UVALive6434_Number Assignment

最新文章

热门文章