HDU3480(기울기 dp)

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
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
제목은 N개의 원소를 포함하는 하나의 집합을 M 서브집합으로 나누어 각 서브집합의 최대치와 최소치의 제곱차와 최소 사고방식을 나타낸다. 먼저 정렬해야 한다는 것이 뚜렷하다. 정렬이 끝난 후에 마치 hdu2829가 dp[i][j]를 설정한 것처럼 느껴진다. 이것은 앞의 i개수를 j조로 나누는 최소 비용을 나타낸다.그래서 전이 방정식은 dp[i][j]=min{dp[k][j-1]+(num[i]-num[k+1])*(num[i]-num[k+1])} 그리고 경사율을 최적화하면 AC 코드:

#include
using namespace std;
#define ll long long
const int maxn = 10010;
int num[maxn];
int dp[maxn][5005];
int N,M,head,tail;
int que[maxn];
int getfz(int i,int j,int k)
{
  return dp[i][k]-dp[j][k]+num[i+1]*num[i+1]-num[j+1]*num[j+1];
}
int getfm(int i,int j)
{
  return num[i+1]-num[j+1];
}
int main()
{
  int T,ncase=1;
  scanf("%d",&T);
  while(T--)
  {
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)scanf("%d",&num[i]);
    sort(num+1,num+N+1);

    for(int i=1;i<=N;i++)dp[i][1]=(num[i]-num[1])*(num[i]-num[1]);
    for(int j=2;j<=M;j++)
    {
      head=tail=0;
      que[tail++]=j-1;
      for(int i=j;i<=N;i++)
      {
        while(head+11],que[head],j-1)<=2*num[i]*getfm(que[head+1],que[head]))head++;
        dp[i][j]=dp[que[head]][j-1]+(num[i]-num[que[head]+1])*(num[i]-num[que[head]+1]);
        while(head+11],j-1)*getfm(que[tail-1],que[tail-2])<=getfz(que[tail-1],que[tail-2],j-1)*getfm(i,que[tail-1]))tail--;
        que[tail++]=i;
      }
    }
    printf("Case %d: %d
",ncase++,dp[N][M]);
  }
  return 0;
}