hdu 1421 침실 옮 기기 (DP + 사고)

침실 을 옮기다
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 15437    Accepted Submission(s): 5215
Problem Description
침실 을 옮 기 는 것 은 매우 힘 들 었 습 니 다. xhd 는 깊이 느 꼈 습 니 다. 시간 은 2006 년 7 월 9 일 을 추 술 했 습 니 다. 그날 xhd 는 어 쩔 수 없 이 27 번 건물 에서 3 번 건물 로 옮 겨 야 했 습 니 다. 10 일 에 건물 을 막 아야 하기 때 문 입 니 다. 침실 안의 n 가지 물건 을 보고 xhd 는 멍 해 지기 시 작 했 습 니 다. n 은 2000 보다 작은 정수 이기 때문에 너무 많 습 니 다. 그래서 xhd 는 2 * k 건 을 마음대로 옮 기기 로 결 정 했 습 니 다. 하지만 피곤 할 것 입 니 다.2 * k 도 작 지 않 기 때문에 n 보다 크 지 않 은 정수 입 니 다. 다행히도 xhd 는 다년간 의 짐 을 옮 긴 경험 에 의 하면 매번 옮 기 는 피로 도 는 좌우 손의 물건 의 무게 차 의 제곱 과 정비례 하 는 것 을 발 견 했 습 니 다. 예 를 들 어 xhd 왼손 은 무게 가 3 인 물건 을 들 고 오른손 은 무게 가 6 인 물건 을 들 고 있 습 니 다.그 는 이번 피로 도 를 (6 - 3) ^ 2 = 9 로 옮 겼 다. 지금 불쌍 한 xhd 는 이 2 * k 개의 물건 을 옮 긴 후 가장 좋 은 상태 가 어떤 지 (즉 가장 낮은 피로 도) 알려 주세요.
 
Input
각 조 의 입력 데 이 터 는 두 줄 이 있 고 첫 번 째 줄 은 두 개의 수 n, k (2 < = 2 * k < = n < 2000) 가 있 습 니 다. 두 번 째 줄 은 n 개의 정수 로 각각 n 개의 물품 의 무 게 를 표시 합 니 다 (무 게 는 2 ^ 15 보다 작은 정수).
 
Output
각 그룹의 입력 데이터 에 대응 하여 출력 데 이 터 는 그의 최소 피로 도 를 나타 내 는 줄 이 하나 밖 에 없다.
 
Sample Input

   
   
   
   

    
    
    
    2 1
1 3
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    4
   
   
   
   

 
Author
xhd
 
Source
ACM 여름 캠프 연습 경기 (2)
 
Recommend
lcy   |   We have carefully selected several similar problems for you:   1176  1058  2084  1069  1203 
 
제목:
중국어 문 제 는 그만 두 겠 습 니 다.
생각:
아이고.중요 한 건 생각 이 야.사고방식 은 정말 기묘 한 것 이다.워 터 DP 경험 상상태 표시 가 생각 나 기 쉽다.dpi [i] [j] 는 이전 i 개 아 이 템 에서 j 를 선택 한 최소 체력 소 비 를 나타 낸다.하지만 이 상 태 는 전혀 옮 길 수 없다.dp [i] [j] 는 앞의 결 과 를 이용 할 수 없 기 때문이다.앞 에 그 물건 들 이 다 쓰 인 줄 몰 랐 기 때문이다.아이고.어찌 할 수 없다.오랫동안 사색 하 다.붕괴블 로 그 를 검색 하 다.열 어 봐.정렬f**k！내 가 왜 그 생각 을 못 했 지!그렇게 많은 해 동안 공짜 로 밥 을 먹었다 니!정렬 이 순간적으로 선택 문 제 를 해결 했다.dp [i] [j] 상태 에 두 개의 소스 가 있 습 니 다.하 나 는 i 번 째 아 이 템 을 사 용 했 습 니 다.하 나 는 제 i 아 이 템 을 사용 하지 않 는 다.
제 i 의 아 이 템 을 사용 한 경우.그 는 틀림없이 제 i - 1 의 물품 과 조합 한 것 이다.왜 일 까요?제 i 개 아 이 템 과 제 x 아 이 템 조합 x < i - 1 을 가정 합 니 다.제 i - 1 개 아 이 템 과 제 y 개 아 이 템 조합 y < i - 1.대 가 는 (w [i] - w [x]) ^ 2 + (w [i - 1] - w [y]) ^ 2 분명히 없어 (w [i] - w [i - 1]) ^ 2 + (w [x] - w [y]) ^ 2 우.그림 을 그리 면 알 수 있다.수축 에서 점차 증가 하 는 네 개의 점 을 취하 여 보면 알 수 있다.그래서 제 i 개 아 이 템 을 가 져 온 경우 dp [i] [j] = dp [i - 2] [j - 1] + (w [i] - w [i - 1]) ^ 2. 제 i 개 아 이 템 을 가 져 오지 않 은 경우 dp [i] [j] = dp [i - 1] [j] 가 분명 합 니 다.그래서 dp [i] [j] = min (dp [i - 2] [j - 1] + (w [i] - w [i - 1]) ^ 2, dp [i - 1] [j]).
코드 참조;

#include<algorithm>
#include<iostream>
#include<string.h>
#include<sstream>
#include<stdio.h>
#include<math.h>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
//#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const double PI=acos(-1.0);
const int maxn=100010;
typedef __int64 ll;
ll ob[2010],dp[2010][1010];
ll pow2(ll x){ return x*x; }
int main()
{
    int n,k,i,j,lim;
    while(~scanf("%d%d",&n,&k))
    {
        memset(dp,0x3f,sizeof dp);//      !!
        for(i=1;i<=n;i++)
            scanf("%I64d",&ob[i]),dp[i][0]=0;
        sort(ob+1,ob+n+1);
        for(i=2,dp[0][0]=0;i<=n;i++)
            for(j=1,lim=min(i/2,k);j<=lim;j++)
                dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+pow2(ob[i]-ob[i-1]));
        printf("%I64d
",dp[n][k]);
    }
    return 0;
}