HDU 3480 Division(斜率优化+二维DP)

                Division

                      Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 999999/400000 K (Java/Others)
                             Total Submission(s): 3984    Accepted Submission(s): 1527

Problem Description
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

HDU 3480 Division(斜率优化+二维DP)

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. 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.
 
Output
For
each test case, output one line containing exactly one integer, the
minimal total cost. Take a look at the sample output for 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.

 
Source
 

【思路】

斜率优化+分配式DP。

设f[i][j]表示将前i个分作j个集合所得最小消费,则有转移方程式:

f[i][j]=min{ f[k][j-1]+(A[k]-A[j+1])^2 }

若有k>l,且决策k优于决策l则有:

f[k][j-1]-f[l][j-1]+sq(A[k+1])-sq(A[l+1]) <= 2*(A[k+1]-A[l+1])*A[i]

先进行j循环枚举f[][j],每一层维护一个单调队列即可。

乘除耗费时间悬殊,如果直接除这个题就超时了。

【代码】

 #include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std; typedef double Do;
const int N = 1e4+;
const int M = +; int f[N][M],A[N],q[N];
int n,m,L,R;
int sq(int x) { return x*x; }
int UP(int l,int k,int j) {
return f[k][j-]-f[l][j-]+sq(A[k+])-sq(A[l+]);
}
int DN(int l,int k,int j) {
return *(A[k+]-A[l+]);
}
void read(int& x) {
char c=getchar(); while(!isdigit(c)) c=getchar();
x=; while(isdigit(c)) x=x*+c-'' , c=getchar();
}
int main() {
int T,kase=;
read(T);
while(T--) {
read(n),read(m);
for(int i=;i<=n;i++) read(A[i]);
sort(A+,A+n+);
for(int i=;i<=n;i++) f[i][]=sq(A[i]-A[]); //初始化第一层
for(int j=;j<=m;j++) {
L=R=;
for(int i=;i<=n;i++) {
while(L<R && UP(q[L],q[L+],j)<=A[i]*DN(q[L],q[L+],j)) L++;
int t=q[L];
f[i][j]=f[t][j-]+sq(A[i]-A[t+]);
while(L<R && UP(q[R-],q[R],j)*DN(q[R],i,j)>=UP(q[R],i,j)*DN(q[R-],q[R],j)) R--;
q[++R]=i;
}
}
printf("Case %d: %d\n",++kase,f[n][m]);
}
return ;
}
上一篇:Oracle Job定时任务的使用详解


下一篇:Centos 7安装oracle 11g R2问题及解决方法汇总