HDU 1421 침실 문제 풀이 보고서

침실 을 옮기다
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 13414 Accepted Submission(s): 4533
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

Author

xhd

解题思路：

题目意思为求n个物品，拿k对使得消耗的体力最少，或者说是这k对物品，每一对中两件物品的质量差平方最小，所以要使得质量差的平方小，只能排序后取质量相邻两个物品作为一对；

现在设f[i][j]为前i件物品组成k对所消耗的体力最小；

这时分两种情况含有第i件物品和不含有第i件物品（即第i件物品是不是含在第j对里）

1.含有i件物品则有 f[i][j]=f[i-2][j-1]+(val[i]-val[i-1])*(val[i]-val[i-1]);

2.不含第i件物品则有 f[i][j]=f[i-1][j];

所以动态转移方程为:f[i][j]=minn(f[i-2][j-1]+(val[i]-val[i-1])*(val[i]-val[i-1]), f[i][j]=f[i-1][j]);

代码如下：

#include 
#include 
#define size 2005
#define INIF 2147483646


int f[size][1005];
int minn(int a,int b)
{
    return a<=b?a:b;
}
int cmp(const void *a,const void *b)
{
	return *(int *)a-*(int *)b;//       
}
int main()
{
    int n,k,i,j;
    int val[size]={0};
    f[0][0]=0;
    while(scanf("%d%d",&n,&k)!=EOF)
    {

        val[0]=0;
        for(i=1; i<=n; i++)
            scanf("%d",&val[i]);
        qsort(val+1,n,sizeof(val[0]),cmp);
        for(i=0; i<=n; i++)
            for(j=1; j<=k; j++)
                f[i][j]=INIF;

        for(i=2; i<=n; i++)
            for(j=1; j*2<=i; j++)
                f[i][j]=minn(f[i-2][j-1]+(val[i]-val[i-1])*(val[i]-val[i-1]),f[i-1][j]);
        printf("%d
",f[n][k]);
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

바 이 두 의 별 2015 첫 경기 (1) 1003 시퀀스 변환

우 리 는 서열 A 에서 서열 B 로 변환 하 는 대 가 를 cost (A, B) = max (| Ai − Bi |) (1 ≤ i ≤ N) 로 정의 합 니 다. 각 조: 첫 번 째 행위 서열 A 의 길이 N (1 ≤...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

HDU 1421 침실 문제 풀이 보고서

좋은 웹페이지 즐겨찾기