P1103 책 정리【dp】

제목 설명
Frank는 깔끔함을 매우 좋아하는 사람이다.그는 책더미와 책꽂이를 가지고 있어서 책을 책꽂이에 놓으려고 한다.책꽂이는 모든 책을 내려놓을 수 있기 때문에 Frank는 먼저 책을 높이 순서대로 책꽂이에 배열한다.그러나 Frank는 많은 책의 폭이 다르기 때문에 책이 매우 가지런하지 않은 것처럼 보인다는 것을 발견했다.그래서 그는 책꽂이가 좀 가지런해 보일 수 있도록 K권의 책을 꺼내기로 결정했다.책꽂이의 불순도는 이렇게 정의된다. 두 권의 책 너비의 차이의 절대값의 합이다.예를 들어 4권의 책이 있다. 1x25x3 2x4 3x1그러면 Frank는 그것을 가지런히 배열한 다음: 1x2 2x4 3x1 5x3의 가지런하지 않은 정도는 2+3+2=7이다. 모든 책의 높이가 다르다는 것을 알고 있으니 k권의 책을 제거한 후의 가장 작은 가지런하지 않은 정도를 구해 주십시오.
입력 형식:
첫 번째 줄에 두 개의 숫자 n과 k가 있는데 책이 몇 권 있다는 것을 의미한다. 그 중에서 몇 권 아래의 n줄을 빼고 한 줄에 두 개의 숫자는 한 권의 높이와 너비를 나타낸다. 모두 200보다 작다.반복되지 않는 높이 보장
출력 형식:
한 줄의 정수는 책꽂이의 최소 불순도를 나타낸다.
데이터 범위:
(1<=n<=100)
전형적인 dp문제보급이지만 dp를 할 줄 모르는 나는 어쨌든 정해를 생각해 내지 못했다.원래 f[i][j]는 제i호 책으로 미루었다는 뜻(짠 물고기의 생각: dp는 생각이 없으면 f[i][j])을 설정한다. 앞에서 j권을 뽑았고 i권의 책을 뽑을지 말지를 고려했다.그러나 죽을 힘을 다해 방정식을 옮길 생각을 하지 못했다.나중에 문제풀이를 보고 문득 깨달았다. 원래 문제는 n-k책을 넣고 혼란을 구하는 것으로 바뀔 수 있었다.이렇게 해서 우리는 f[i][j]로 하여금 i권의 책을 삽입했다고 표시했다. 그 중에서 마지막 책은 j이고 전이 방정식은 f[i][j]=min{f[i-1][e]}(i-1<=e<=j-1)이다.
이 이야기는 dp문제가 매우 교활해서 생각해 내지 못하면 거꾸로 생각하라는 것을 알려준다. 마치 [P1280닉의 임무]와 같다.
코드는 다음과 같습니다.

#include
#include
#include
#include
#include
using namespace std;
struct node{
    int h,w;
}a[110];
int f[101][101];
bool cmp(node a,node b)
{
    return a.h>b.h;
}
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].h,&a[i].w);
    }
    sort(a+1,a+n+1,cmp);
    memset(f,0x7f,sizeof(f));
    for(int i=1;i<=n;i++)
    {
        f[1][i]=0;
    }
    for(int i=1;i<=n-k;i++)
    {
        for(int j=i;j<=n;j++)
        {
            for(int k=i-1;k1][k]+abs(a[j].w-a[k].w));
            }
        }
    }
    int minn=1e9;
    for(int i=1;i<=n;i++)
    {
        minn=min(minn,f[n-k][i]);
    }
    printf("%d",minn);
    return 0;
}

ps: 蒟蒻dp 열심히 닦아야 해요. 왜냐하면 pty 대신은 200 도 dp 닦아야 입문할 수 있어요.noip 적어도 100점 있어. 괜히 하지 마.