首页 > ACM题库 > HDU-杭电 > HDU 3480-Division-动态规划-[解题报告]HOJ
2014
04-04

HDU 3480-Division-动态规划-[解题报告]HOJ

Division

问题描述 :

Little D is really interested in the theorem of sets recently. There’s a problem that confused him a long time.  
Let T be a set of integers. Let the MIN be the minimum integer in T and MAX be the maximum, then the cost of set T if defined as (MAX � MIN)^2. Now given an integer set S, we want to find out M subsets S1, S2, …, SM of S, such that

Code

and the total cost of each subset is minimal.

输入:

The input contains multiple test cases.
In the first line of the input there’s an integer T which is the number of test cases. Then the description of T test cases will be given.
For any test case, the first line contains two integers N (≤ 10,000) and M (≤ 5,000). N is the number of elements in S (may be duplicated). M is the number of subsets that we want to get. In the next line, there will be N integers giving set S.

输出:

The input contains multiple test cases.
In the first line of the input there’s an integer T which is the number of test cases. Then the description of T test cases will be given.
For any test case, the first line contains two integers N (≤ 10,000) and M (≤ 5,000). N is the number of elements in S (may be duplicated). M is the number of subsets that we want to get. In the next line, there will be N integers giving set S.

样例输入:

2
3 2
1 2 4
4 2
4 7 10 1

样例输出:

Case 1: 1
Case 2: 18


Hint
The answer will fit into a 32-bit signed integer.

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3480

题目大意:现在给出一个包含N(1<N<10000)个数字的集合,现在需要把这个数字集合分成M(1<M<5000)个两两不想交的集合,这些集合的并集为全集。每个集合的权值为集合中最大数见最小数的平方,现在求所有集合和的最小值。

解题思路:先将全集中的数字进行排序,可以判断的是,要使总权值最小,子集中的数字必然是排序后连续的数字。之后可以进行动态规划,但是时间复杂度是O(N*M^2),明显会TLE。

我们在考虑如何进行优化,对于这种问题,我们有两种优化方式,斜率优化和四边形优化,对于将数字排序后,两种方法都适用,我采用第二种方法。

通过代码:

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define N 10003
#define M 5002
using namespace std;
int f[N][M];
int s[N][M];
int a[N];
int main(){
    int T,n,m;
    scanf("%d",&T);
    for (int cas=1;cas<=T;cas++){
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        for (int i=1;i<=n;i++){
            f[i][1]=(a[i]-a[1])*(a[i]-a[1]);
            s[i][1]=1;
        }
        for (int i=2;i<=m;i++){
            s[n+1][i]=n-1;
            for (int j=n;j>=i;j--){
                f[j][i]=-1;
                for (int k=s[j][i-1];k<=s[j+1][i];k++){
                    int tp=f[k][i-1]+(a[j]-a[k+1])*(a[j]-a[k+1]);
                    if (f[j][i]==-1||f[j][i]>tp){
                        f[j][i]=tp;
                        s[j][i]=k;
                    }
                    //printf("%d %d %d %d %d\n",i,j,k,f[j][i],s[j][i]);
                }
            }
        }
        printf("Case %d: %d\n",cas,f[n][m]);
    }
    return 0;
}

参考:http://blog.csdn.net/ruptins/article/details/21415133


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。