[IOI2000][DP] 우체국 문제

noi문제고에서 산간지역건초등학교[openjudge7624]라는 문제에 수차례 학대를 받은 후에 이 IOI의 원제를 보았습니다. 저는 2000년에 입대할 수 있을지도 모른다는 감탄을 금치 못했습니다. =||||좋습니다. 우선 이 문제는 첨가호 유형인 DP라는 것을 한눈에 알 수 있습니다.

그래서 우리는 자연스럽게 아래의 방정식을 생각했다.

f[i][j] = min(f[k][j - 1] + dis[k + 1][i], f[i][j]);

여기서 f[i][j]는 전 i개 도시에 j개 우체국을 건설하는 것이 가장 좋은 방법임을 나타낸다. k는 단점 위치

이다.
그럼 디스 그룹은 어떻게 구합니까? 우리는 다음과 같은 방정식이 있습니다.
dis[i][j] = dis[i][j - 1] + a[j] - a[(i + j)/2];

여기서 dis[i][j]는 도시 i에서 j까지 우체국을 설립하는 것이 가장 좋은 방법이고 a는 각 도시의 좌표

이다.
그럼 왜 디스[i][j]가 디스[i][j-1]에서 구할 수 있는지 설명해 주세요.우선 욕심 전략에서 알 수 있듯이 일부 도시에 우체국을 세울 때 가장 중간에 있는 하나를 선택하면 가장 좋은 것으로 구체적으로 증명된다.2. 그러면 왜 이전 상태에서 넘어올 수 있는지, 우선 우리는 i가 j-1의 도시에 우체국을 k로 배치한 것을 고려했다. 새로 가입한 도시 j에 대해 우리는 위치를 k에서 k+1으로 옮겼고 X=a[k+1]-a[k]를 설정했다. 그러면 [i,k]의 마을에 대해 거리마다 X가 많아졌다. [k+1,j]의 마을에 대해 하나하나 X가 없어졌기 때문에 우리는 도대체 이동할지 안 할지 고려할 것이다.3. 제1조의 증명과 결합하면 이 답안은 a[j]-a[(i+j)/2]만 추가됩니다.4. 증명 완료

코드:

#include 
#define INF 100000000
using namespace  std;
inline int read(int & t)
{
    register char ch; t = 0; register bool flag = 0;
    while (!((((ch = getchar()) >= '0') && (ch <= '9')) || (ch == '-')));
    ch == '-' ? flag = 1 : t = ch - '0';
    while (((ch = getchar()) >= '0') && (ch <= '9')) t = t * 10 + ch - '0';
    if (flag) t = -t;
}
inline void write(int t)
{
    if (t < 0) {putchar('-'); t = -t;}
    if (t >= 10) write(t / 10);
    putchar(t % 10 + '0');
}
int n, m;
int dis[320][320];
int f[320][40], a[320];
int main()
{
    read(n); read(m);
    memset(f, 0, sizeof(f));
    memset(dis, 0, sizeof(dis));
    for (int i = 1; i <= n; i ++)
        read(a[i]);
    for (int i = 1; i <= n; i ++)
        for (int j = i + 1; j <= n; j ++)
            dis[i][j] = dis[i][j - 1] + a[j] - a[(i + j) / 2];
    for (int i = 1; i <= n; i ++)
        f[i][1] = dis[1][i];
    for (int j = 2; j <= m; j ++)
        for (int i = 1; i <= n; i ++)
        {
            f[i][j] = INF;
            for (int k = 1; k < i; k ++)
                f[i][j] = min(f[k][j - 1] + dis[k + 1][i], f[i][j]);
        }
    write(f[n][m]);
}

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

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

【POJ 1160】Post Office

There are no two villages in the same position. Post offices will be built in some, but not necessarily all of the villa...

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

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

[IOI2000][DP] 우체국 문제

그래서 우리는 자연스럽게 아래의 방정식을 생각했다.

코드:

좋은 웹페이지 즐겨찾기