hdu 3480 Division傾斜最適化

5645 ワード
傾斜最適化
リンク:http://acm.hdu.edu.cn/showproblem.php?pid=3480
ディヴィジョン
Time Limit:10000/5000 MS(Java/Others)    メモリLimit:99999/40000 K(Java/Others)Total Submission(s):3864    Acceepted Submission(s):1479
Problem Description
リトルD is really interested in the orem 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 maximm,the n the cot of set t T＿if defined as(MAX-MIN)^2.Now given an integer set S,we to find Mbsets S 1,SM ats S 1

and the total cost of each subset is minimal.
 
Input
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.The n 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.M is the number of subsets we to vint.Inrsext.Insell nell ingeltxt.
 
Output
For each test case,output one line containing exactlyone integer,the minimal total cost.Take a look at the sample out format.
 
Sample Input
 
   

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

Sample Output 
 
   

     Case 1: 1 Case 2: 18 
    
 
     
 
      Hint 
     
The answer will fit into a 32-bit signed integer.

题意：把n个数字  分成m个集合。  每个集合的价值是 这个集合中  (max-min)^2。 输出最少的价值


做法：如果想价值最小，不妨先排个序。这样 最后的答案肯定在排序后的数组中 是连续的。

可以得到数组  dp[i][c]=min{dp[j][c-1]+(num[i]-num[j+1])^2

直接dp 复杂度 N*N*M   瞬间爆炸。


可以斜率优化来写；

推导出   

y(j)=dp[j][c-1]+num[j+1]*num[j+1]

x(j)=num[j+1]

当 k

[y(j)-y(k)]/[x[k]-x[j]]<=2*num[i]


当不等式成立是，j的取值更优。


#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#include 
#include 
#include 
#include 
#include 
#include 

#define inf 0x7f7f77f
#define ll __int64

int num[10100];
int dp[10100][6010];
int que[10100];

int cc;
int y(int j)
{
    return dp[j][cc-1]+num[j+1]*num[j+1];
}

int main()
{
    int n,m;
    int t;
    scanf("%d",&t);
    int cas=1;
    while(t--)
    {
        scanf("%d%d",&n,&m);//  m 
        memset(dp,0,sizeof dp);
        
        dp[0][0]=0;
        dp[0][1]=0;
        for(int i=1;i<=n;i++)
        {
            //num[i]=i;
            scanf("%d",num+i);
            
            dp[i][0]=0;
        } 

        sort(num+1,num+1+n);
        for(int i=1;i<=n;i++)
            dp[i][1]=(num[i]-num[1])*(num[i]-num[1]);//   0        0

        for(int c=2;c<=m;c++)//   c 
        {
            int tou=0,wei=0;
            que[wei++]=c-1;
            cc=c;
            for(int i=c;i<=n;i++)//  //  i>=j
            { 
                while(wei-tou>=2)
                {
                    int a=que[tou];
                    int b=que[tou+1];
                    int y1=y(a);
                    int y2=y(b); 
                    int x1=num[a+1];
                    int x2=num[b+1];
                    

                    if((y2-y1)<=2*num[i]*(x2-x1)) 
                        tou++;
                    else
                        break;
                }

                int tem=que[tou];
                dp[i][c]=dp[tem][c-1]+(num[i]-num[tem+1])*(num[i]-num[tem+1]);
            
                while(wei-tou>=2)//g(b,a)>g(c,b)
                {
                    int a=que[wei-2];
                    int b=que[wei-1];
                    int c=i;
                    int y1=y(a);
                    int y2=y(b);
                    int y3=y(c);
                    int x1=num[a+1];
                    int x2=num[b+1];
                    int x3=num[c+1];
                    if((y2-y1)*(x3-x2)>=(x2-x1)*(y3-y2))
                        wei--;
                    else
                        break;
                }
                que[wei++]=i;
            }
            //puts("");
        }
        printf("Case %d: %d
",cas++,dp[n][m]);
    }
    return 0;
}
【3点】【清華合宿2015】電球
Default Value Attribute Based Approach to Property Initializton